2019 CCPC 网络选拔赛

^&^

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Bit operation is a common computing method in computer science ,Now we have two positive integers A and B ,Please find a positive integer C that minimize the value of the formula (A  xor  C)  &  (B  xor  C) .Sometimes we can find a lot of C to do this ,So you need to find the smallest C that meets the criteria .

For example ,Let’s say A is equal to 5 and B is equal to 3 ,we can choose C=1,3…. ,so the answer we’re looking for C is equal to 1.

If the value of the expression is 0 when C=0, please print 1.

InputThe input file contains T test samples.(1<=T<=100)

The first line of input file is an integer T.

Then the T lines contains 2 positive integers, A and B, (1≤A,B<232) 
OutputFor each test case,you should output the answer and a line for each answer.

Sample Input

1
3 5

Sample Output

1

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const ll INF=(ll)1e18+100;
ll a,b;
void solve(){
    scanf("%lld%lld",&a,&b);
    ll ans=a&b;
    if(ans==0) ans=1;
    printf("%lld\n",ans);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

 


array

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

You are given an array a1,a2,…,an(∀i∈[1,n],1≤ai≤n). Initially, each element of the array is **unique**.

Moreover, there are m instructions.

Each instruction is in one of the following two formats:

1. (1,pos),indicating to change the value of apos to apos+10,000,000;
2. (2,r,k),indicating to ask the minimum value which is **not equal** to any ai ( 1≤i≤r ) and **not less ** than k.

Please print all results of the instructions in format 2.

InputThe first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.

In each test case, there are two integers n(1≤n≤100,000),m(1≤m≤100,000) in the first line, denoting the size of array a and the number of instructions.

In the second line, there are n distinct integers a1,a2,…,an (∀i∈[1,n],1≤ai≤n),denoting the array.
For the following m lines, each line is of format (1,t1) or (2,t2,t3).
The parameters of each instruction are generated by such way :

For instructions in format 1 , we defined pos=t1⊕LastAns . (It is promised that 1≤pos≤n)

For instructions in format 2 , we defined r=t2⊕LastAns,k=t3⊕LastAns. (It is promised that 1≤r≤n,1≤k≤n )

(Note that ⊕ means the bitwise XOR operator. )

Before the first instruction of each test case, LastAns is equal to 0 .After each instruction in format 2, LastAns will be changed to the result of that instruction.

(∑n≤510,000,∑m≤510,000 ) 
OutputFor each instruction in format 2, output the answer in one line. 
Sample Input

3
5 9
4 3 1 2 5 
2 1 1
2 2 2
2 6 7
2 1 3
2 6 3
2 0 4
1 5
2 3 7
2 4 3
10 6
1 2 4 6 3 5 9 10 7 8 
2 7 2
1 2
2 0 5
2 11 10
1 3
2 3 2
10 10
9 7 5 3 4 10 6 2 1 8 
1 10
2 8 9
1 12
2 15 15
1 12
2 1 3
1 9
1 12
2 2 2
1 9

Sample Output

1
5
2
2
5
6
1
6
7
3
11
10
11
4
8
11

Hint
note:
After the generation procedure ,the instructions of the first test case are :
2 1 1, in format 2 and r=1 , k=1
2 3 3, in format 2 and r=3 , k=3
2 3 2, in format 2 and r=3 , k=2
2 3 1, in format 2 and r=3 , k=1
2 4 1, in format 2 and r=4 , k=1
2 5 1, in format 2 and r=5 , k=1
1 3  , in format 1 and pos=3
2 5 1, in format 2 and r=5 , k=1
2 5 2, in format 2 and r=5 , k=2

the instructions of the second test case are :
2 7 2, in format 2 and r=7 , k=2
1 5  , in format 1 and pos=5
2 7 2, in format 2 and r=7 , k=2
2 8 9, in format 2 and r=8 , k=9
1 8  , in format 1 and pos=8
2 8 9, in format 2 and r=8 , k=9

the instructions of the third test case are :
1 10   , in format 1 and pos=10
2 8 9  , in format 2 and r=8 , k=9
1 7    , in format 1 and pos=7
2 4 4  , in format 2 and r=4 , k=4
1 8    , in format 1 and pos=8
2 5 7  , in format 2 and r=5 , k=7
1 1    , in format 1 and pos=1
1 4    , in format 1 and pos=4
2 10 10, in format 2 and r=10 , k=10
1 2    , in format 1 and pos=2

因为数组中的值唯一,且在1到n的范围内,而询问的r和k也在1到n的范围内。 所以对于任意一个被操作1修改过的值都不会成为询问的答案,而询问的结果也必然在k到n+1的范围内。 因为没有被修改过值是唯一的,所以可以建立权值线段树,维护权值区间内的值所在下标的最大值。而询问则转化为不小于k的值里面,下标超过r的最小权值是多少。

如何处理询问呢,一种较为暴力的解法是直接在线段树上询问权值在k到n+1的范围内第一个下标超过r的权值是多少。但复杂度可能会被卡,需要减枝。
再加上一个额外的判断就可以了,就是在递归查询完左子树内存不存在大于r的下标之后,如果不存在,则先看一下右子树内的下标的最大值是否大于r。如果不大于r,则不必再进入右子树内查询,否则答案一定在右子树内。
在进左子树之前也利用同样的判断条件来判断是否有必要进入左子树,这样做可以保证单次查询的复杂度是O(log n) 的。 而对于操作1,则等价于修改某个权值的下标为无穷大。
操作复杂度也是O(log n )的。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define delf int mid=(l+r)>>1
typedef long long ll;
const int maxn=(int)1e5+100;
const int INF=(int)1e9+7;
int n,m,a[maxn];
struct node{
    int l,r,sum;
}tree[maxn*40];
int root[maxn],tot,tree_num[maxn*20];
inline int read(){
    int x = 0;
    char c = getchar();
    bool flag = 0;
    while(!isdigit(c)) {
        if(c == '-')
            flag = 1;
        c = getchar();
    }
    while(isdigit(c)) {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return flag ? -x : x;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void insert(int &o,int pos,int l,int r,int val){
    if(!o){
        o=++tot;
        tree[o].sum=tree[o].l=tree[o].r=0;
    }
    tree[o].sum=tree[pos].sum;
    tree[o].sum++;
    if(l==r) return; delf;
    if(val<=mid){
        tree[o].r=tree[pos].r;
        insert(tree[o].l,tree[pos].l,l,mid,val);
    }
    else{
        tree[o].l=tree[pos].l;
        insert(tree[o].r,tree[pos].r,mid+1,r,val);
    }
}
void insert_num(int o,int l,int r,int val){
    tree_num[o]=min(tree_num[o],val);
    if(l==r) return ;
    delf;
    if(val<=mid) insert_num(o<<1,l,mid,val);
    else insert_num(o<<1|1,mid+1,r,val);
}
void build(){rep(i,1,n) insert(root[i],root[i-1],1,n+1,a[i]);}
int query(int o,int l,int r,int ql,int qr){
    if(ql>r||l>qr) return INF;
    int len=r-l+1,tt;
    if(ql<=l&&r<=qr){
        if(tree[o].sum!=len){
            int l1=l,r1=r,pos=o;
            while(l1!=r1){
                int mid=(l1+r1)/2;
                if(mid-l1+1>tree[tree[pos].l].sum) pos=tree[pos].l,r1=mid;
                else pos=tree[pos].r,l1=mid+1;
            }
            return l1;
        }
        else return INF;
    }
    delf;
    return ((tt=query(tree[o].l,l,mid,ql,qr))==INF?query(tree[o].r,mid+1,r,ql,qr):tt);
}
int query_num(int o,int l,int r,int ql,int qr){
    if(ql>r||l>qr) return INF;
    if(ql<=l&&r<=qr) return tree_num[o];
    delf;
    return min(query_num(o<<1,l,mid,ql,qr),query_num(o<<1|1,mid+1,r,ql,qr));
}
void init(){
    tot=0;
    rep(i,1,n) root[i]=0;
    rep(i,1,n*8) tree_num[i]=INF;
}
void solve(){
    n=read();m=read();
    rep(i,1,n) a[i]=read();
    init(); build();
    int last_ans=0;
    rep(i,1,m){
        int op;op=read();
        if(op==1){
            int tt;tt=read();
            insert_num(1,1,n+1,a[tt^last_ans]);
        }
        else{
            int r,k;r=read();k=read();
            r^=last_ans; k^=last_ans;
            printf("%d\n",last_ans=min(query_num(1,1,n+1,k,n+1),query(root[r],1,n+1,k,n+1)));
        }
    }
}
int main(){
    int T;T=read();
    while(T--) solve();
}

 


Shuffle Card

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

A deck of card consists of n cards. Each card is different, numbered from 1 to n. At first, the cards were ordered from 1 to n. We complete the shuffle process in the following way, In each operation, we will draw a card and put it in the position of the first card, and repeat this operation for m times.

Please output the order of cards after m operations. 

InputThe first line of input contains two positive integers n and m.(1<=n,m<=105)

The second line of the input file has n Numbers, a sequence of 1 through n.

Next there are m rows, each of which has a positive integer si, representing the card number extracted by the i-th operation. 
OutputPlease output the order of cards after m operations. (There should be one space after each number.) 

Sample Input

5 3
1 2 3 4 5
3
4
3

Sample Output

3 4 1 2 5

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const ll INF=(ll)1e18+100;
int n,m,flag[maxn],a[maxn];
void solve(){
    memset(flag,0,sizeof(flag));
    rep(i,1,n) scanf("%d",&a[1]);
    rep(i,1,m){
        scanf("%d",&a[i]);
    }
    dep(i,m,1){
        if(!flag[a[i]]){
            flag[a[i]]=1;
            printf("%d ",a[i]);
        }
    }
    rep(i,1,n) if(!flag[i]){
        printf("%d ",i);
    }
}
int main(){
    while(~scanf("%d%d",&n,&m)) solve();
}

 


Windows Of CCPC

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

In recent years, CCPC has developed rapidly and gained a large number of competitors .One contestant designed a design called CCPC Windows .The 1-st order CCPC window is shown in the figure:

And the 2-nd order CCPC window is shown in the figure:

We can easily find that the window of CCPC of order k is generated by taking the window of CCPC of order k−1 as C of order k, and the result of inverting C/P in the window of CCPC of order k−1 as P of order k.
And now I have an order k ,please output k-order CCPC Windows , The CCPC window of order k is a 2k∗2k matrix. 
InputThe input file contains T test samples.(1<=T<=10)

The first line of input file is an integer T.

Then the T lines contains a positive integers k , (1≤k≤10) 

OutputFor each test case,you should output the answer . 

Sample Input

3
1
2
3

Sample Output

CC
PC
CCCC
PCPC
PPCC
CPPC
CCCCCCCC
PCPCPCPC
PPCCPPCC
CPPCCPPC
PPPPCCCC
CPCPPCPC
CCPPPPCC
PCCPCPPC

签到

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
char s[1500][1500]; 
void gao(int x){
    if(x==2){
        s[1][2]=s[2][2]=s[1][1]='C';
        s[2][1]='P';
        return;
    }
    gao(x/2);
    x/=2;
    for(int i=1;i<=x;i++){
        for(int j=1+x;j<=x+x;j++){
            s[i][j]=s[i][j-x];
        }
    }
    for(int i=1+x;i<=x+x;i++){
        for(int j=1+x;j<=x+x;j++){
            s[i][j]=s[i-x][j-x];
        }
    }
    for(int i=1+x;i<=x+x;i++){
        for(int j=1;j<=x;j++){
            if(s[i-x][j]=='C') s[i][j]='P';
            else s[i][j]='C';
        }
    }
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        n=(1<<n);
        gao(n);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                printf("%c",s[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

 


Fishing Master

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Heard that eom is a fishing MASTER, you want to acknowledge him as your mentor. As everybody knows, if you want to be a MASTER’s apprentice, you should pass the trial. So when you find fishing MASTER eom, the trial is as follow:

There are n fish in the pool. For the i – th fish, it takes at least ti minutes to stew(overcook is acceptable). To simplify this problem, the time spent catching a fish is kminutes. You can catch fish one at a time and because there is only one pot, only one fish can be stewed in the pot at a time. While you are catching a fish, you can not put a raw fish you have caught into the pot, that means if you begin to catch a fish, you can’t stop until after k minutes; when you are not catching fish, you can take a cooked fish (stewed for no less than ti) out of the pot or put a raw fish into the pot, these two operations take no time. Note that if the fish stewed in the pot is not stewed for enough time, you cannot take it out, but you can go to catch another fish or just wait for a while doing nothing until it is sufficiently stewed.

Now eom wants you to catch and stew all the fish as soon as possible (you definitely know that a fish can be eaten only after sufficiently stewed), so that he can have a satisfying meal. If you can complete that in the shortest possible time, eom will accept you as his apprentice and say “I am done! I am full!”. If you can’t, eom will not accept you and say “You are done! You are fool!”.

So what’s the shortest time to pass the trial if you arrange the time optimally? 
InputThe first line of input consists of a single integer T(1≤T≤20), denoting the number of test cases.

For each test case, the first line contains two integers n(1≤n≤105),k(1≤k≤109), denoting the number of fish in the pool and the time needed to catch a fish.

the second line contains n integers, t1,t2,…,tn(1≤ti≤109) ,denoting the least time needed to cook the i – th fish. 
OutputFor each test case, print a single integer in one line, denoting the shortest time to pass the trial. 

Sample Input

2
3 5
5 5 8
2 4
3 3

Sample Output

23
11

Hint
Case 1: Catch the 3rd fish (5 mins), put the 3rd fish in, catch the 1st fish (5 mins), wait (3 mins),  

take the 3rd fish out, put the 1st fish in, catch the 2nd fish(5 mins), 

take the 1st fish out, put the 2nd fish in, wait (5 mins), take the 2nd fish out.

Case 2: Catch the 1st fish (4 mins), put the 1st fish in, catch the 2nd fish (4 mins),  

take the 1st fish out, put the 2nd fish in, wait (3 mins), take the 2nd fish out.

随便贪心一下,每条鱼都需要被抓上来并且煮足够的时间,而我们能在炖鱼的时候抓鱼,所以至少需要抓一条鱼的时间和炖所有鱼的时间。
要能在这个时间内就完成,则除了抓第一条鱼以外抓鱼的时候锅里都必须在炖鱼(假设锅里的鱼一旦炖好就自动取出来),显然如果 都太小的时候这是不能做到的,会有一些抓鱼的时间锅里没有在炖鱼,我们称锅里没有炖鱼的抓鱼时间为被浪费的时间,所以我们的优化目标就是使被浪费的总时间T最小。

对于第 条鱼,炖它的时候我们可以不浪费时间抓到ti/k条鱼,或者浪费k-ti%k的时间抓到ti/k+1条鱼。所以如果 sum(ti/k)>=n-1,则可以不浪费时间完成任务,否则差m条鱼就选炖ti%k前m大的鱼的时候浪费时间多抓一条鱼。

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

long long cas,z,x;
long long  n,m,w,h,a[100100],sum;

bool cmp(long long yi,long long er)
{
    return yi>er;
}

int main()
{
    scanf("%lld",&cas);
    while (cas--)
    {
        scanf("%lld%lld",&z,&x);
        sum=x;n=0;
        for (int i=1;i<=z;i++) 
        {
            scanf("%lld",&a[i]);
            sum+=a[i];
            n+=a[i]/x;
            a[i]=a[i]%x;
        }
        if (n<z-1) 
        {
            sort(a+1,a+z+1,cmp);
            for (int i=1;i<=z-1-n;i++)
              sum+=x-a[i];
        }
        
        printf("%lld\n",sum);
    }
    return 0;
}

 

发表评论,支持MarkDown语法