[20181107][模拟赛]
程序员文章站
2022-05-17 23:53:25
T1
思路
考虑一下每个数会与其他位置的哪些数字遇到。显然每隔gcd(n,m,k)个数都会遇到一次。所以只要看一下将给出的所有数字全部对gcd(n,m,k)取模是否能包含从0到gcd(n,m,k) - 1的所有数就行了。 ......
[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("%d\n",ans[i]); return 0; }