2017 Multi-University Training Contest

2017 Multi-University Training Contest - Team 5

阅读量：6579 次

发布时间：2019-06-24

本文共 3683 字，大约阅读时间需要 12 分钟。

---恢复内容开始---

rank:77/758

1001 Rikka with Candies

因为没有手写bitset被卡了一下，最后过了。

#include 
      
       const long long mod = 1e9+7;const double ex = 1e-10;#define inf 0x3f3f3f3fusing namespace std;typedef pair
       
          pii;bitset<50005> A;bitset<50005> B;bitset<50005> an;vector 
        
          E;int ans[50005];int ansid[50005];int main(){    int t;    scanf("%d",&t);    int c;    int maxa;    while (t--){        int N,M,Q;        scanf("%d%d%d",&N,&M,&Q);        A.reset();        B.reset();        maxa = 0;        for (int i = 1; i<=N; i++){            scanf("%d",&c);            A[c] = 1;            maxa = max(maxa,c);        }        E.clear();        for (int i = 0; i<=maxa ;i++) ans[i] = -1;        for (int i = 1;i<=M; i++){            scanf("%d",&c);            E.push_back(make_pair(c,-1));        }        for (int i = 1;i<=Q;i++){            scanf("%d",&c);            E.push_back(pii(c,i));        }        sort(E.begin(),E.end());        for (int i = E.size()-1 ; i>=0; i--)        {            c = E[i].first;            if (E[i].second == -1){            for (int j = 0;j<=maxa;j+=c)                B[j] = !B[j];            }            else{                int id = E[i].second;                if (c>maxa) ansid[id] = 0;                else{                    if (ans[c]!=-1) ansid[id] = ans[c];                    else                    {                      an = (A>>c)&(B);                      ans[c] = (an.count()) % 2;                      ansid[id] = ans[c];                    }                }            }        }        for (int i = 1;i<=Q;i++)            printf("%d\n",ansid[i]);    }    return 0;}

View Code

1006

贪心构造

#include 
      
       using namespace std;int T;long long n,m;int main(){    scanf("%d",&T);    while (T--) {        scanf("%I64d%I64d",&n,&m);        if (n==1) {            puts("0");            continue;        }        if (n==2) {            puts("2");            continue;        }        if (m

View Code

1008

枚举，反向考虑每个元素对之后的贡献。

#include 
      
       const long long mod = 1e9+7;const double ex = 1e-10;#define inf 0x3f3f3f3fusing namespace std;long long M[10005];long long TM[10005];int main(){    int T;    scanf("%d",&T);    while (T--)    {        int n,m;        scanf("%d%d",&n,&m);        for (int i = 0; i<=m; i++)             TM[i] = 0;        for (int i= 0; i<=m;i++)        {            long long z;            scanf("%I64d",&z);            M[i] = z;        }        int tmp = 0;        TM[0] = 1;        for (int i = 1; i<=n ;){            if (M[tmp]>TM[tmp])            {                printf("%d%c",tmp,i==n?'\n':' ');                for (int j = m; j>=0;j--){                    TM[j+tmp] = TM[j+tmp] + TM[j];                }                i++;            }            else            {                tmp++;            }        }    }    return 0;}

View Code

1011

倒着递推一波即可。

#include 
      
       #define maxn 100010#define inf 0x3f3f3f3f#define REP(i,x,y) for(int i=x;i<(y);i++)#define RREP(i,x,y) for(int i=x;i>(y);i--)using namespace std;typedef long long ll;typedef pair
       
         pii;int n,k,a[maxn],win[maxn];set
        
         S;int main(){    int T;scanf("%d",&T);    while(T--) {        S.clear();        memset(win,0,sizeof(win));        scanf("%d %d",&n,&k);        REP(i,1,n+1) {            scanf("%d",&a[i]);        }        sort(a+1,a+1+n);        int ans=1;        win[n]=1;        RREP(i,n-1,0) {            if(win[i+1]==1&&a[i+1]-a[i]<=k) {                win[i]=1;                ans++;            }        }        cout<
         
          <