「codechef」January Lunchtime 2015
统计每个字母出现次数，取最大值，判断其是否等于l/2
|
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 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; int num[205]; char ch[55]; int main() { T=read(); while(T--) { scanf("%s",ch+1); int l=strlen(ch+1),mx=0; memset(num,0,sizeof(num)); for(int i=1;i<=l;i++) { num[ch[i]]++; mx=max(mx,num[ch[i]]); } if(mx==l/2&&l%2==0)puts("YES"); else puts("NO"); } return 0; } |
乘法快速乘即可，但乘方由于M过大。。使用欧拉函数降幂比较麻烦。。
发现
a^(10b+c)
= (a^b)^10 * a^c
然后就能On算出表达式了
^10可以看做常数
|
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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; ll M; char ch[10005]; ll mul(ll a,ll b) { ll ans=0;a%=M; for(ll i=b;i;i>>=1,a=(a+a)%M) if(i&1)ans=(ans+a)%M; return ans%M; } ll qpow(ll a,ll b) { ll ans=1;a%=M; for(ll i=b;i;i>>=1,a=mul(a,a)) if(i&1)ans=mul(ans,a); return ans%M; } ll pow(int a,int b,int c,int d) { ll tmp=0,ans=1; for(int i=a;i<=b;i++) tmp=(mul(tmp,10)+ch[i]-'0')%M; for(int i=c;i<=d;i++) { ans=mul(qpow(ans,10),qpow(tmp,ch[i]-'0')); } return ans; } ll solve(ll l,ll r,ll num) { for(int i=r;i>=l;i--) if(ch[i]=='*') { if(ch[i-1]!='*')return mul(solve(l,i-1,1),solve(i+1,r,num)); else { int j=i-2; while(ch[j]!='*'&&j)j--; ll res=pow(j+1,i-2,i+1,r); if(j==0)return res; if(ch[j-1]=='*')return solve(l,j-2,res); else return mul(solve(l,j-1,1),res); } } ll tmp=0; for(int i=l;i<=r;i++)tmp=(mul(tmp,10)+ch[i]-'0')%M; if(num==1)return tmp; else return qpow(tmp,num); } int main() { T=read(); while(T--) { M=read(); scanf("%s",ch+1); int l=strlen(ch+1); printf("%lld\n",solve(1,l,1)); } return 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 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,d; int bin[20],num[20]; ll dp[2<<16]; void solve() { for(int i=0;i<bin[n];i++)dp[i]=1e60; dp[0]=0; for(int i=0;i<bin[n];i++) { int tmp=i,t1=0,t2=0; for(int j=n;j;j--) { num[j]=tmp/bin[j-1]; tmp%=bin[j-1]; t1^=num[j];t2+=num[j]; } for(int j=0;j<=n;j++) if(num[j]) dp[i]=min(dp[i],dp[i-bin[j-1]]); dp[i]+=(ll)t1*t2; } } int main() { T=read(); while(T--) { bin[0]=1; n=read();d=read(); for(int i=1;i<=n;i++) bin[i]=bin[i-1]*d; solve(); printf("%lld\n",dp[bin[n]-1]); } return 0; } |
这一题比较有意思
将宗族大小分为<=300 和 >300
用数组统计大小为1-300的宗族个数，询问时暴力
记>300的宗族数为tot，设询问数为x
若没有取模，则ans+=tot*x
若有一个>300的宗族，设人数为y
则询问在0-y之间答案不变
y-2y之间答案减少y
以此类推
这部分用树状数组统计
|
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 63 64 65 66 67 68 69 70 71 72 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; ll tot; ll t[100005],c[305]; void add(int x,ll val) { for(int i=x;i<=100000;i+=i&-i) t[i]+=val; } ll query(int x) { ll ans=0; for(int i=x;i;i-=i&-i) ans+=t[i]; return ans; } void solve_add(int x,ll val) { if(x<=300)c[x]+=val; else { tot+=val; for(int i=x;i<=100000;i+=x) add(i,val*(-x)); } } ll solve_query(ll x) { ll ans=0; for(int i=1;i<=300;i++) ans+=x%i*c[i]; ans=ans+tot*x+query(x); return ans; } int main() { n=read(); int x,y;char ch[2]; for(int i=1;i<=n;i++) { x=read();y=read(); solve_add(x,y); } m=read(); while(m--) { scanf("%s",ch+1); x=read(); if(ch[1]=='?')printf("%lld\n",solve_query(x)); else if(ch[1]=='+')solve_add(x,1); else solve_add(x,-1); } return 0; } |
Subscribe
计数器 9854045
OI 课件=>
OI 课件=>