2017 Multi-University Training Contest

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

rank:77/758

1001 Rikka with Candies

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

#include <bits/stdc++.h>
const long long mod = 1e9+7;
const double ex = 1e-10;
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int>  pii;
bitset<50005> A;
bitset<50005> B;
bitset<50005> an;
vector <pii> 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
",ansid[i]);
    }
    return 0;
}

View Code

#include <bits/stdc++.h> 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<n-1) { printf("%I64d ",2LL*m+2LL*m*(m-1)+(n*(n-1)-2LL*m-m*(m-1))*n); } else if (m<n*(n-1)/2) { printf("%I64d ",2LL*m+(n*(n-1)-2*m)*2LL); } else { printf("%I64d ",n*(n-1)); } } return 0; }

#include <bits/stdc++.h> const long long mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f using 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?' ':' '); for (int j = m; j>=0;j--){ TM[j+tmp] = TM[j+tmp] + TM[j]; } i++; } else { tmp++; } } } return 0; }

#include <bits/stdc++.h> #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<int,int> pii; int n,k,a[maxn],win[maxn]; set<int>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<<ans<<endl; } }

2017 Multi-University Training Contest

相关推荐