BestCoder Round #84
1001 Aaronson
对n做二进制拆分，注意m对30取min
|
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<map> #include<set> #include<ctime> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define lb long double #define mod 1000000007 #define inf 9000000000000000000LL 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,m; int bin[35]; int main() { bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1; T=read(); while(T--) { n=read();m=read(); int ans=0; for(int i=min(30,m);i>=0;i--) { ans+=n/bin[i]; n%=bin[i]; } printf("%d\n",ans); } return 0; } |
1002 Bellovin
直接输出F，显然是字典序最小的方案
|
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 |
#include<map> #include<set> #include<ctime> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define lb long double #define mod 1000000007 #define inf 9000000000000000000LL 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],b[100005]; int ans[100005]; int main() { T=read(); while(T--) { memset(ans,127,sizeof(ans)); ans[0]=0; n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++) { int t=lower_bound(ans,ans+n+1,a[i])-ans-1; b[i]=t+1; ans[t+1]=min(ans[t+1],a[i]); } for(int i=1;i<=n;i++) if(i!=n)printf("%d ",b[i]); else printf("%d",b[i]); puts(""); } return 0; } |
1003 Colmerauer
用单调栈预处理下每个点向左/右第一个小等于它的元素，向上/下第一个大等于它的元素（一开始我用set预处理结果TLE）。
然后计算每个元素对答案的贡献，若设四个方向第一个使得其不能成为鞍点的数与其的距离分别为L,R,U,D
则其对答案的贡献为L*R*U*D*(L+R+1)*(U+D+1)/4
|
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 81 82 83 84 85 86 87 88 89 90 91 |
#include<map> #include<set> #include<ctime> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define lb long double #define UI unsigned int #define mod (1LL<<32) #define inf 1000000000 #define N 100000 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,m; int a[1005][1005],L[1005][1005],R[1005][1005],U[1005][1005],D[1005][1005]; pair<int,int>t[1005]; void getans() { UI ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { ll l=j-L[i][j],r=R[i][j]-j,u=i-U[i][j],d=D[i][j]-i; ll t=l*r*u*d*(l+r)*(u+d)/4; ans+=a[i][j]*t%mod; } cout<<ans<<endl; } int main() { T=read(); while(T--) { n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(); stack<int>st; for(int i=1;i<=n;i++) { a[i][0]=a[i][m+1]=-inf; while(!st.empty())st.pop();st.push(0); for(int j=1;j<=m;j++) { while(!st.empty()&&a[i][st.top()]>a[i][j])st.pop(); L[i][j]=st.top(); st.push(j); } while(!st.empty())st.pop();st.push(m+1); for(int j=m;j>=1;j--) { while(!st.empty()&&a[i][st.top()]>a[i][j])st.pop(); R[i][j]=st.top(); st.push(j); } } for(int i=1;i<=m;i++) { a[0][i]=a[n+1][i]=inf; while(!st.empty())st.pop();st.push(0); for(int j=1;j<=n;j++) { while(!st.empty()&&a[st.top()][i]<a[j][i])st.pop(); U[j][i]=st.top(); st.push(j); } while(!st.empty())st.pop();st.push(n+1); for(int j=n;j>=1;j--) { while(!st.empty()&&a[st.top()][i]<a[j][i])st.pop(); D[j][i]=st.top(); st.push(j); } } getans(); } return 0; } |
1004 Dertouzos
注意到满足题设条件的数一定是d的倍数kd，且k不大于d的最小因子，k*d小于n，且k是素数，预处理素数表后在其中二分即可
|
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<map> #include<set> #include<ctime> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define lb long double #define mod 1000000007 #define inf 9000000000000000000LL #define N 100000 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; } bool a[N+5]; int p[N+5]; void primelist() { a[0]=a[1]=1; for(int i=2;i<N;i++) if(!a[i]) { p[++p[0]]=i; for(int j=i*2;j<N;j+=i) a[j]=1; } } int T,n,d; int solve(int d,int x) { for(int i=1;p[i]<=x;i++) if(d%p[i]==0)return p[i]; return x; } int main() { primelist(); T=read(); while(T--) { n=read();d=read(); int t=solve(d,n/d); if(t*d==n)t--; int ans=upper_bound(p+1,p+p[0]+1,t)-p-1; printf("%d\n",ans); } return 0; } |
计数器 9318255
OI 课件=>
OI 课件=>
黄学长 03的贡献为什么是L*R*U*D*(L+R+1)*(U+D+1)/4
其实就是求包含一个点的子矩形面积和对吧
可以行列分开，算完乘起来
对于左侧的L个格子，右端点可以是R个格子中的一个
那么右侧的贡献就是(1+2+…+R)*L = (R+1)*L/2
左侧类似，算一下加起来就行咯