http:codeforces.comcontest834

Walking through the streets of Marshmallow City, Slastyona have spotted some merchants selling a kind of useless toy which is very popular nowadays– caramel spinner! Wanting to join the craze, she has immediately bought the strange contraption.

Spinners in Sweetland have the form of V-shaped pieces of caramel. Each spinner can, well, spin around an invisible magic axis. At a specific point in time, a spinner can take 4 positions shown below (each one rotated 90 degrees relative to the previous, with the fourth one followed by the first one):

技术分享

After the spinner was spun, it starts its rotation, which is described by a following algorithm: the spinner maintains its position for a second then majestically switches to the next position in clockwise or counter-clockwise order, depending on the direction the spinner was spun in.

Slastyona managed to have spinner rotating for exactlynseconds. Being fascinated by elegance of the process, she completely forgot the direction the spinner was spun in! Lucky for her, she managed to recall the starting position, and wants to deduct the direction given the information she knows. Help her do this.


Input

There are two characters in the first string– the starting and the ending position of a spinner. The position is encoded with one of the following characters:v(ASCII code118, lowercase v),(ASCII code60),^(ASCII code94) or(ASCII code62) (see the picture above for reference). Characters are separated by a single space.

In the second strings, a single numbernis given (0?≤?n?≤?109)– the duration of the rotation.

It is guaranteed that the ending position of a spinner is a result of ansecond spin in any of the directions, assuming the given starting position.


Output

Outputcw, if the direction is clockwise,ccw– if counter-clockwise, andundefinedotherwise.


Examples
input
^ 
1

output
cw

input
 ^
3

output
ccw

input
^ v
6

output
undefined

题意:给出开始和结束的方向,还有次数,问你是顺时针还是逆时针转到,不确定的话输出nudefine;

代码:

#includeiostream
#includecstring
#includecstdio 
#includecmath
#includealgorithm 
#includeiomanip
#includevector
#define ld long double
#define ll long long
const int inf=0x3f3f3f3f; 
const int maxn=1e3+5; 
using namespace std;
int n;
char a,b;
 int slove(char x)
 {
     if(x==v)return 0;
     else if(x==)return 1;
     else if(x==^)return 2;
     else return 3;
 }
int main()
{
    scanf("%c %c",a,b);
    scanf("%d",n);
    int tmp1=slove(a);
    int tmp2=slove(b);
//    couttmp1" "tmp2endl;
    if((tmp1+n)%4==tmp2((tmp1-n)%4+4)%4==tmp2)
    {
        printf("undefined\n");return 0;
    }
    if((tmp1+n)%4==tmp2)
    {
        printf("cw\n");return 0;
    }
    if(((tmp1-n)%4+4)%4==tmp2)
    {
        printf("ccw\n");return 0;
    }
    printf("undefined\n");
    return 0; 
} 

B. The Festive Evening
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

技术分享

It‘s the end of July– the time when a festive evening is held at Jelly Castle! Guests from all over the kingdom gather here to discuss new trends in the world of confectionery. Yet some of the things discussed here are not supposed to be disclosed to the general public: the information can cause discord in the kingdom of Sweetland in case it turns out to reach the wrong hands. So it‘s a necessity to not let any uninvited guests in.

There are 26 entrances in Jelly Castle, enumerated with uppercase English letters fromAtoZ. Because of security measures, each guest is known to be assigned an entrance he should enter the castle through. The door of each entrance is opened right before the first guest‘s arrival and closed right after the arrival of the last guest that should enter the castle through this entrance. No two guests can enter the castle simultaneously.

For an entrance to be protected from possible intrusion, a candy guard should be assigned to it. There areksuch guards in the castle, so if there are more thankopened doors, one of them is going to be left unguarded! Notice that a guard can‘t leave his post until the door he is assigned to is closed.

Slastyona had a suspicion that there could be uninvited guests at the evening. She knows the order in which the invited guests entered the castle, and wants you to help her check whether there was a moment when more thankdoors were opened.


Input

Two integers are given in the first string: the number of guestsnand the number of guardsk(1?≤?n?≤?106,1?≤?k?≤?26).

In the second string,nuppercase English letterss1s2...snare given, wheresiis the entrance used by thei-th guest.


Output

Output ?YES? if at least one door was unguarded during some time, and ?NO? otherwise.

You can output each letter in arbitrary case (upper or lower).


Examples
input
5 1
AABBB

output
NO

input
5 1
ABABB

output
YES



Note

In the first sample case, the door A is opened right before the first guest‘s arrival and closed when the second guest enters the castle. The door B is opened right before the arrival of the third guest, and closed after the fifth one arrives. One guard can handle both doors, as the first one is closed before the second one is opened.

In the second sample case, the door B is opened before the second guest‘s arrival, but the only guard can‘t leave the door A unattended, as there is still one more guest that should enter the castle through this door.

题意:有26个们和K个门卫,给你入场顺序,看是否有某个时候至少有一扇门没有守卫;

题解:找到没扇门关闭的最后时刻然后模拟;

#includeiostream
#includecstring
#includecstdio 
#includecmath
#includealgorithm 
#includeiomanip
#includevector
#define ld long double
#define ll long long
const int inf=0x3f3f3f3f; 
const int maxn=1e6+5; 
using namespace std;
char a[maxn];
int b[27];
bool vis[27];
int n,k;
int main()
{
    scanf("%d %d",n,k);
    scanf("%s",a);
    for(int i=0;in;i++)
    {
        b[a[i]-A]=i;
    }
    bool flag=true;
    for(int i=0;in;i++)
    {
        if(!vis[a[i]-A])
        {
            k--;
            vis[a[i]-A]=true;
            if(k0)
            {
                flag=false;break;
            }
            if(i==b[a[i]-A])k++;
        }
        else if(i==b[a[i]-A])
        {
            k++;
        }
    }
    if(flag)puts("NO");
    else puts("YES");
}

C. The Meaningless Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

技术分享

Slastyona and her loyal dog Pushok are playing a meaninglessgamethat is indeed very interesting.

Thegameconsists of multiplerounds. Its rules are very simple: in each round, a natural numberkis chosen. Then, the one who says (or barks) it faster than the other wins theround. After that, the winner‘s score is multiplied byk2, and the loser‘s score is multiplied byk. In the beginning of thegame, both Slastyona and Pushok have scores equal to one.

Unfortunately, Slastyona had lost her notepad where the history of allngameswas recorded. She managed to recall the final results for each games, though, but all of her memories of them are vague. Help Slastyona verify their correctness, or, to put it another way, for each given pair of scores determine whether it was possible for a game to finish with such result or not.


Input

In the first string, the number of gamesn(1?≤?n?≤?350000)is given.

Eachgameis represented by a pair of scoresa,b(1?≤?a,?b?≤?109)– the results of Slastyona and Pushok, correspondingly.


Output

For each pair of scores, answer "Yes" if it‘s possible for a game to finish with given score, and "No" otherwise.

You can output each letter in arbitrary case (upper or lower).


Example
input
6
2 4
75 45
8 8
16 16
247 994
1000000000 1000000

output
Yes
Yes
Yes
No
No
Yes



Note

Firstgamemight have been consisted of one round, in which the number2would have been chosen and Pushok would have won.

The secondgameneeds exactly two rounds to finish with such result: in the first one, Slastyona would have said the number5, and in the second one, Pushok would have barked the number3.

题意:玩游戏,开始是都是1,每轮选一个数k,一个乘k,另一个乘k^2,;给a,b两个数,看是否是某个游戏的结果;

题解:比赛当时没想用二分去找,分解因数超时了。只要a*b==x^3(a/x)*(b/x)==x就可以了;

#includeiostream
#includecstring
#includecstdio 
#includecmath
#includealgorithm 
#includeiomanip
#includevector
#define ld long double
#define ll long long
const int inf=0x3f3f3f3f; 
const int maxn=1e6+5; 
const ll N=1e18; 
using namespace std;
ll num[maxn]; 
int n;
ll x,y;
ll slove(ll l,ll r,ll m)
{
    while(l=r)
    {
        ll mid=(l+r)1; 
        if(num[mid]==m)return mid; 
        else if(num[mid]m)
        {
            r=mid-1; 
        }
        else
        {
            l=mid+1; 
        } 
    //    coutl" "rendl; 
    }
    return -1;    
}
int main()
{
    scanf("%d",n);
    ll cnt; 
    for(cnt=1;cnt*cnt*cnt=N;cnt++)
    num[cnt]=cnt*cnt*cnt; 
    while(n--)
    {
        scanf("%I64d %I64d",x,y);
         ll ans=slove(1,cnt-1,x*y); 
        if((x/ans)*(y/ans)==ans)
        {
            puts("Yes");
        }
        else
        {
            puts("No");
        }
    }
    return 0;
}

D. The Bakery
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

技术分享

Some time ago Slastyona the Sweetmaid decided to open her own bakery! She bought required ingredients and a wonder-oven which can bake several types of cakes, and opened the bakery.

Soon the expenses started to overcome the income, so Slastyona decided to study the sweets market. She learned it‘s profitable to pack cakes in boxes, and that the moredistinctcake types a box contains (let‘s denote this number as thevalueof the box), the higher price it has.

She needs to change the production technology! The problem is that the oven chooses the cake types on its own and Slastyona can‘t affect it. However, she knows the types and order ofncakes the oven is going to bake today. Slastyona has to pack exactlykboxes with cakes today, and she has to put in each box several (at least one) cakes the oven produced oneright after another(in other words, she has to put in a box a continuous segment of cakes).

Slastyona wants to maximize the total value of all boxes with cakes. Help her determine this maximum possible total value.


Input

The first line contains two integersnandk(1?≤?n?≤?35000,1?≤?k?≤?min(n,?50))– the number of cakes and the number of boxes, respectively.

The second line containsnintegersa1,?a2,?...,?an(1?≤?ai?≤?n)– the types of cakes in the order the oven bakes them.


Output

Print the only integer– the maximum total value of all boxes with cakes.


Examples
input
4 1
1 2 2 1

output
2

input
7 2
1 3 3 1 4 4 4

output
5

input
8 3
7 7 8 7 7 8 1 7

output
6



Note

In the first example Slastyona has only one box. She has to put all cakes in it, so that there are two types of cakes in the box, so the value is equal to2.

In the second example it is profitable to put the first two cakes in the first box, and all the rest in the second. There are two distinct types in the first box, and three in the second box then, so the total value is5.



题意:给你一个序列,分成K段让求每一段不同的数的数目的和最大

题解:最开始想简单了,用set贪心去做到后面发现不对,这题正确解法是dp+线段树,dp[i][j]表示分成i段在j的最大值,转移方程dp[i][j]=max(dp[i-1][j])0jj;可以用线段树的query直接求的

我们用last[i]代表a[i]上次出现的位置,然后每次对last[i]~i的位置全加1,代码如下

#includeiostream
#includecstring
#includecstdio 
#includecmath
#includealgorithm 
#includeiomanip
#includevector
#define ld long double
#define ll long long
using namespace std;
const int maxn=4e4+5e3+5; 
int n,k; 
int a[maxn];
int now[maxn],last[maxn]; 
int add[maxn2]; 
int dp[55][maxn]; 
int tree[maxn2]; 
void push(int rt)
{
    tree[rt]=max(tree[rt1],tree[rt1|1]);
    return; 
} 
void push_down(int rt)
{
    if(add[rt])
    {
        add[rt1]+=add[rt];
        add[rt1|1]+=add[rt];
        tree[rt1]+=add[rt];
        tree[rt1|1]+=add[rt];
        add[rt]=0; 
    } 
    return ; 
} 
void update(int L,int R,int c,int l,int r,int rt)
{
    if(L=lr=R)
    {
        tree[rt]+=c; 
        add[rt]+=c;
        return ; 
    } 
    push_down(rt); 
    int m=(l+r)/2;
    if(L=m)
    update(L,R,c,l,m,rt1);
    if(Rm)
    update(L,R,c,m+1,r,rt1|1);
    push(rt); 
    return ; 
} 
int query(int L,int R,int l,int r,int rt)
{
    if(L=lr=R)
    {
        return tree[rt]; 
    } 
    push_down(rt);
    int m=(l+r)1;
    int ans=0; 
    if(Rm)
        ans=max(ans,query(L,R,m+1,r,rt1|1));
    if(L=m)
        ans=max(ans,query(L,R,l,m,rt1));
    return ans;  
} 
int main()
{
    scanf("%d %d",n,k);
    for(int i=1;i=n;i++)
    {
        scanf("%d",a[i]); 
    }
    for(int i=1;i=n;i++)
    {
        last[i]=now[a[i]];
        now[a[i]]=i; 
    }
    for(int i=1;i=k;i++)
    {
        memset(tree,0,sizeof(tree));
        memset(add,0,sizeof(add)); 
        for(int j=1;j=n;j++)
        {
            update(j,j,dp[i-1][j],0,n,1); 
        } 
        for(int j=i;j=n;j++)
        {
            update(max(i-1,last[j]),j-1,1,0,n,1);
            dp[i][j]=query(i-1,j-1,0,n,1); 
        } 
    } 
    printf("%d\n",dp[k][n]); 
    return 0; 
























http://codeforces.com/contest/834

原文地址:http://www.cnblogs.com/lhclqslove/p/7264714.html


最新回复(0)
/jishuMbCBW9_2BYgLdLGFrqaK5vtLmYy6eDQ9Xj9JsvSQ_3D_3D4719321
8 简首页