雪崩啊。。。FST了两题数组下标打错。。
A. A Serial Killer
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <bits/stdc++.h> using namespace std; string s,t; int n; int main() { cin>>s>>t; cout<<s<<" "<<t<<endl; scanf("%d",&n); while(n--){ string tmp1,tmp2;cin>>tmp1>>tmp2; if(tmp1==s) {s=tmp2;cout<<s<<" "<<t<<endl;} else {t=tmp2;cout<<s<<" "<<t<<endl;} } } |
B. Sherlock and his girlfriend
随便构造一下,合数为2,质数为1就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <bits/stdc++.h> #define maxn 100010 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; bool isprime[maxn]; int prime[maxn],num_prime; void getprime(ll n) { memset(isprime,true,sizeof(isprime)); isprime[0]=0,isprime[1]=0; for(int i=2;i<n;i++){ if(isprime[i]) prime[num_prime++]=i; for(int j=0;j<num_prime&&prime[j]*i<n;j++){ isprime[i*prime[j]]=false; if(i%prime[j]==0) break; } } } int n; int vis[maxn]; int main() { getprime(100010); scanf("%d",&n); for(int i=2;i<=n+1;i++){ if(isprime[i]) { vis[i]=1; } else vis[i]=2; } if(n!=1&&n!=2) printf("%d\n",2); else puts("1"); for(int i=2;i<=n+1;i++) { if(i!=2) printf(" "); printf("%d",vis[i]); } } |
C. Molly’s Chemicals
题意:给出n个数字a[]和一个k,求区间和为k的次幂的区间有多少个。N<=1e5,1<=|k|<=10,-1e9<a[i]<1e9。
因为区间和最大为1e14,最小为-1e14,所以这个k的次幂的指数大概不会超过50.把所有的在范围内的K次幂全部算出来。然后维护一个前缀和,把搞过的前缀和放到map里面去。对于每个前缀和都减去一个k次幂的数看是否在Map里能找到就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <bits/stdc++.h> #define maxn 100010 using namespace std; typedef long long ll; const ll inf=100000000000000LL; int n,k,a[maxn]; ll sum[maxn],kk[maxn]; map<ll,int>ma; int main() { scanf("%d %d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } kk[0]=1; int cnt=1; if(abs(k)!=1){ for(int i=1;;i++){ kk[i]=kk[i-1]*k; if((kk[i]*k>0&&kk[i]*k>inf)||(kk[i]*k<0&&kk[i]*k<-inf)) break; cnt++; } } else{ if(k==-1) {cnt=1;kk[1]=-1;} else cnt=0; } ll ans=0; ma[0]=1LL; for(int i=1;i<=n;i++){ for(int j=0;j<=cnt;j++){ ll tmp2=sum[i]-kk[j]; if(ma.count(tmp2)) ans+=(ll)ma[tmp2]; } ma[sum[i]]++; } printf("%I64d\n",ans); } |
D. The Door Problem
题意:有n个门,m个开关,每个门被两个开关控制。给出n个门的初始状态,然后给出每个开关可以控制哪些门。让你判断能否通过操作,可以让所有的门打开。n,m<=1e5
因为每个门都是被两个开关控制,那么把钥匙看成点,门看成边,如果某个门的状态为1,那么也就意味着它所连的两个钥匙必须都选或者都不选。也就是这条边两端的颜色要一样。如果某个门的状态为0,那么他连的两个钥匙必须要只选择一个。也就是这条边两端的颜色不一样。这样建完图后会有一个个连通块,如果每个连通块二染色不会出现矛盾,那么就是可行。否则无解。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <bits/stdc++.h> #define maxn 100010 #define mp make_pair #define inf 0x3f3f3f3f #define REP(i,x,y) for(int i=x;i<y;i++) #define dbg(x) cout<<#x<<" = "<<(x)<<endl; using namespace std; typedef long long ll; typedef pair<int,int> pii; int n,m; vector<pii>e[maxn]; int vis[maxn],p[maxn],c[maxn],vis2[maxn]; struct P{ int v,col; P(){} P(int _v,int _c):v(_v),col(_c){} }; bool bfs(int st,int col){ c[st]=col;vis2[st]=1; queue<P>que;que.push(P(st,col)); while(!que.empty()){ P now=que.front();que.pop(); int Size=e[now.v].size(); REP(i,0,Size){ pii Next=e[now.v][i];int tmp=Next.second; int tmp2=(tmp==1 ? now.col: !now.col); if(c[Next.first]!=-1){ if(c[Next.first]!=tmp2) return false; else continue; } else c[Next.first]=tmp2; vis2[Next.first]=1; que.push(P(Next.first,tmp2)); } } return true; } int main() { scanf("%d %d",&n,&m); REP(i,1,n+1) scanf("%d",&vis[i]); REP(i,1,m+1){ int cnt;scanf("%d",&cnt); REP(j,1,cnt+1){ int u;scanf("%d",&u); if(!p[u]) p[u]=i; else { e[i].push_back(mp(p[u],vis[u])); e[p[u]].push_back(mp(i,vis[u])); } } } int flag=1; memset(c,-1,sizeof(c)); REP(i,1,m+1){ if(!vis2[i]) flag=bfs(i,1); if(!flag) break; } if(flag) puts("YES"); else puts("NO"); } |
E. The Holmes Children
题意:略。。太长了。。
首先(x,y)满足x+y=n和gcd(x,y)=1的话,那么gcd(x+y,y)=1,所以gcd(n,y)=1.所以满足的y就是。这个反证法证一证就好了。。。f(n)=
。
然后g()那个函数就是g(n)=n。
然后我们就需要求一个这样的东西,大概是(k+1)/2左右。而这个暴力算logn次就变成1了。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <bits/stdc++.h> #define mod 1000000007 #define inf 1e13 using namespace std; typedef long long ll; ll n,k; ll phi(ll n){ ll ans=n; for(ll i=2;i*i<=n;i++){ if(n%i==0){ ans=ans/i*(i-1); while(n%i==0) n/=i; } } if(n>1) ans=ans/n*(n-1); return ans; } int main() { scanf("%I64d %I64d",&n,&k); ll ans=n; for(ll i=1LL;i<=k;i++){ if(i%2) ans=phi(ans); if(ans==1) break; } printf("%I64d\n",ans%mod); } |