[20181107][模拟赛]

题面

t1

思路

考虑一下每个数会与其他位置的哪些数字遇到。显然每隔gcd(n,m,k)个数都会遇到一次。所以只要看一下将给出的所有数字全部对gcd(n,m,k)取模是否能包含从0到gcd(n,m,k) – 1的所有数就行了。

代码

#include<cstdio> #include<iostream> #include<cstdlib> #include<ctime> #include<queue> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int n = 100000 + 100; ll read() {     ll x = 0, f = 1;     char c = getchar();     while(c < '0' || c > '9') {         if(c == '-') f = -1;         c = getchar();     }     while(c >= '0' && c <= '9') {         x = x * 10 + c - '0';         c = getchar();     }     return x * f; } int n,m,k,a[n],b[n],k[n]; int gcd(int x,int y) {     return !y ? x : gcd(y,x % y); } namespace bf1 {          void main() {         memset(a,0,sizeof(a));         memset(b,0,sizeof(b));         int aa = read();         for(int i = 1;i <= aa;++i) a[read()] = 1;         int bb = read();         for(int i = 1;i <= bb;++i) b[read()] = 1;         read();         for(int i = 0;i <= 100000;++i) {             int x1 = i % n, x2 = i % m;             a[x1] = b[x2] = a[x1] | b[x2];         }         for(int i = 0;i < n;++i) {             if(a[i] != 1) {                 puts("no");                 return;             }         }         for(int i = 0;i < m;++i) {             if(b[i] != 1) {                 puts("no");                 return;             }         }         puts("yes");     } } namespace bf2 {     int tmp[n * 5],js = 0;     void main() {         js = 0;         int mod = gcd(gcd(n,m),k);         int aa = read();         for(int i = 1;i <= aa;++i) tmp[++js] = read() % mod;         int bb = read();         for(int i = 1;i <= bb;++i) tmp[++js] = read() % mod;         int kk = read();         for(int i = 1;i <= kk;++i) tmp[++js] = read() % mod;         int now = 0;         sort(tmp + 1,tmp + js + 1);          tmp[0] = -1;         int ans = 0;         for(int i = 1;i <= js;++i) {             if(tmp[i] == tmp[i-1]) continue;             if(tmp[i] == tmp[i-1]+1) now++;             else {                 ans = max(ans,now);                 now = 1;             }         }         ans = max(ans,now);         if(ans >= mod) puts("yes");         else puts("no");         return;     } } int main() {     freopen("happy2.in","r",stdin);     freopen("happy2.out","w",stdout);     int t = read();     while(t--) {         n = read(),m = read(),k = read();         if(n <= 100 && m <= 100 && k == 0) {             bf1::main();             continue;         }         bf2::main();     }     return 0; }

t2

想了一会感觉不可做，直接55分暴力。

55分代码

#include<cstdio> #include<iostream> #include<cstdlib> #include<ctime> #include<queue> #include<cstring> #include<algorithm> #include<bitset> using namespace std; typedef long long ll; const int n = 300000 + 100; ll read() {     ll x = 0, f = 1;     char c = getchar();     while(c < '0' || c > '9') {         if(c == '-') f = -1;         c = getchar();     }     while(c >= '0' && c <= '9') {         x = x * 10 + c - '0';         c = getchar();     }     return x * f; } int n,p; namespace bf1 {     int du[n];     void main() {         for(int i = 1;i <= n;++i) {             int x = read(), y = read();             du[x]++;             du[y]++;         }         ll ans1 = 0;         for(int i = 1;i <= n;++i)             if(du[i] == 0) ans1++;         cout<<(ll)n * (ll)(n - 1)/2 - (ans1 * (ans1 - 1) / 2);         return;     } } namespace bf2 {     const int nn = 110;     bitset <nn> tmp[nn];     int ans = 0;     inline int check(int x,int y) {         bitset <nn> ls;         ls = tmp[x] | tmp[y];         return ls.count() >= p;     }     void main() {         for(int i = 1;i <= n;++i) {             int x = read(),y = read();             tmp[x][i] = 1;             tmp[y][i] = 1;         }         for(int i = 1;i <= n;++i) {             for(int j = i + 1;j <= n;++j) {                 ans += check(i,j);             }         }         cout<<ans<<endl;     } } int main() {     freopen("suspect.in","r",stdin);     freopen("suspect.out","w",stdout);     n =  read(),p = read();     if(p == 0) {         cout<<((ll)n*(n-1) / 2);         return 0;     }     if(p == 1) {         bf1::main();         return 0;     }     if(n <= 100) {         bf2::main();         return 0;     }     return 0; }

std

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<stack> #include<cstdlib> #define inf 100000000 using namespace std; typedef long long ll; struct edge {     int from,to,pre; }e[1000000]; int h[300005]={0},cou=0; int c[300005],ed[300005]; void addedge(int from,int to) {     cou++;     e[cou]=((edge){from,to,h[from]});     h[from]=cou; }  inline void update(int x) {     if(x==0)     {         c[0]++;         return;     }     for(;x<=300000;x+=x&-x)         c[x]++; } inline int get(int x) {     if(x==-1) return 0;     int sum=0;     for(;x;x-=x&-x)         sum+=c[x];     return sum+c[0]; } int main() {     freopen("suspect.in","r",stdin);     freopen("suspect.out","w",stdout);     ll ans=0;     int sum,i,n,p,a,b,v,j;     cin>>n>>p;     for(i=1;i<=n;i++)     {         scanf("%d%d",&a,&b);         addedge(a,b); addedge(b,a);         ed[a]++; ed[b]++;     }     for(i=1;i<=n;i++)         update(ed[i]);     for(i=1;i<=n;i++)     {         if(ed[i]>=p)             ans+=n-1;         else         {             sum=n-get(p-ed[i]-1);             if(ed[i]>=p-ed[i]) sum--;             for(j=h[i];j;j=e[j].pre)             {                 v=e[j].to;                 if(ed[v]==p-ed[i]) sum--;                 ed[v]--;             }             for(j=h[i];j;j=e[j].pre)             {                 v=e[j].to;                 ed[v]++;             }             ans+=sum;         }     }     cout<<ans/2<<endl;     return 0; }

t3

80分思路

暴力分感觉都可做，然后就写了80分暴力。用莫队卡一下100分？？？会tle吧(真麻烦，不想写)。

100分思路

如果这个题让着求区间出现奇数次的数的异或和就很简单了。所以我们可以对于询问先离线一下。按照右端点拍个序。然后用树状数组维护一下区间异或和。就是从1扫到n，同时将当前的数上一次出现的位置(在树状数组里)异或上这个数。然后查询就好了。

100分代码

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<stack> #include<cstdlib> #include<string> #include<bitset> #include<iomanip> #include<deque> #include<utility> #define inf 1000000000 #define fi first #define se second #define n 1000005 #define p 1000000007 #define debug(x) cerr<<#x<<"="<<x<<endl #define mp(x,y) make_pair(x,y) using namespace std; typedef long long ll; typedef pair<int,int> pii; int c[n],now,sum,a[n],b[n],ans[n],nxt[n],n; map<int,int> vis,pre; vector<pii> q[n];  void add(int x,int w) {     for(;x<=n;x+=x&-x)         c[x]^=w; }  int get(int x) {     int s=0;     for(;x;x-=x&-x)         s^=c[x];     return s; }  int main() {     int i,m,ql,qr,j;     freopen("xor.in","r",stdin);     freopen("xor.out","w",stdout);     cin>>n;     now=0;     for(i=1;i<=n;i++)     {         scanf("%d",&a[i]);         vis[a[i]]++;         nxt[pre[a[i]]]=i;         pre[a[i]]=i;         if(vis[a[i]]>1)             now^=a[i];         b[i]=now;         //debug(b[i]);     }     cin>>m;     for(i=1;i<=m;i++)     {         scanf("%d%d",&ql,&qr);         q[ql].push_back(mp(qr,i));     }     for(i=1;i<=n;i++)     {         //debug(sum);         for(j=0;j<q[i].size();j++)             ans[q[i][j].se]=get(q[i][j].fi)^b[q[i][j].fi];         ql=nxt[i];         if(ql)         {             sum^=a[i];             add(ql,a[i]);         }     }     for(i=1;i<=m;i++)         printf("%dn",ans[i]);     return 0; }

总结

期望得分:100 + 55 + 80 = 235

实际得分:100 + 55 + 80 = 235

暴力没挂真的感动。越来越菜了

一言

那时我怎么都想不到，原来也有这一天，念及你，竟既无风雨也无晴。 ——我亦飘零久