「codechef」April Challenge 2015
BROKPHON
模拟
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define mod 999911657 #define B 200191 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; int a[100005]; bool mark[100005]; int main() { T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++)a[i]=read(); memset(mark,0,sizeof(mark)); int ans=0; for(int i=2;i<=n;i++) if(a[i]!=a[i-1]) mark[i]=mark[i-1]=1; for(int i=1;i<=n;i++) if(mark[i])ans++; printf("%d\n",ans); } return 0; } |
CHEFLCM
所有约数和
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define mod 999911657 #define B 200191 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; ll ans; int main() { T=read(); while(T--) { n=read();ans=0; int t=sqrt(n); for(int i=1;i<=t;i++) if(n%i==0) { ans+=i; if(i*i!=n)ans+=n/i; } printf("%lld\n",ans); } return 0; } |
PIANO1
暴力T T
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define p 1000003 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,l; char ch[105]; void solve() { scanf("%s",ch+1); l=strlen(ch+1); int tot=0,ans=0; for(int i=1;i<=l;i++) if(ch[i]=='T')tot+=2; else tot++; n=read()*12; for(int i=1;i<=n;i++) ans+=(n-i)/tot; printf("%d\n",ans); } int main() { T=read(); while(T--)solve(); return 0; } |
CSEQ
l~r之间每个数的使用次数当作一个变量。。
那么就相当于求方程组sigma(xi)(l<=i<=r)=n的非负整数解数。。然后就是排列组合求和
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define p 1000003 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,l,r,ans; int qpow(ll a,ll b) { ll ans=1; for(int i=b;i;i>>=1,a=a*a%p) if(i&1)ans=ans*a%p; return ans; } ll C(int n,int m) { if(m>n)return 0; m=min(m,n-m); ll s1=1,s2=1; for(int i=0;i<m;i++)s1=s1*(n-i)%p; for(int i=0;i<m;i++)s2=s2*(i+1)%p; return s1*qpow(s2,p-2)%p; } int lucas(int n,int m) { if(m==0)return 1; return C(n%p,m%p)*lucas(n/p,m/p)%p; } void solve() { n=read();l=read();r=read(); int t=r-l+1; printf("%d\n",(lucas(n+t,t)+p-1)%p); } int main() { T=read(); while(T--) solve(); return 0; } |
CARLOS
先用并查集将能够相互转化的并在一起
dp f(i,j)表示前i个末尾为j的最小改动次数
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long 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,m,K,n; int fa[200005],a[200005],f[200005][205]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { T=read(); while(T--) { m=read();K=read();n=read(); for(int i=1;i<=m;i++)fa[i]=i; for(int i=1;i<=K;i++) { int x=read(),y=read(); fa[find(x)]=find(y); } for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++)fa[i]=find(i); for(int i=1;i<=n;i++) { int t=fa[a[i]],mn=inf; for(int j=1;j<=m;j++) { mn=min(f[i-1][j],mn); if(fa[j]!=t)f[i][j]=inf; else f[i][j]=mn+(j!=a[i]); } } int ans=inf; for(int i=1;i<=m;i++)ans=min(ans,f[n][i]); if(ans==inf)puts("-1"); else printf("%d\n",ans); } return 0; } |
FRMQ
除了st表还有神做法么TAT
压常数可过
|
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<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000000000LL #define pa pair<int,int> #define ll long long 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; } ll ans; int bin[20]; int n,m,x,y,t; int Log[100005],a[100005],mx[17][100005]; void pre() { for(int i=0;i<n;i++)mx[0][i]=a[i]; for(int j=1;j<=Log[n];j++) for(int i=n-1;i>=0;i--) mx[j][i]=max(mx[j-1][i],mx[j-1][i+bin[j-1]]); } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; n=read(); Log[0]=-1;for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1; for(int i=0;i<n;i++)a[i]=read(); pre(); m=read();x=read();y=read(); while(m--) { t=y-x; if(t<0) { t=Log[-t+1]; ans+=max(mx[t][y],mx[t][x-bin[t]+1]); } else { t=Log[t+1]; ans+=max(mx[t][x],mx[t][y-bin[t]+1]); } x=x+7; y=y+11; while(x>=n-1)x-=n-1; while(y>=n)y-=n; } cout<<ans<<endl; return 0; } |
计数器 9319372
OI 课件=>
OI 课件=>
有个问题：pre函数里面mx[j-1][i+bin[j-1]]，mx+bin[j-1]是会越界的吧？
好像。。。