2016 ACM – ICPC Shenyang Onsite
一些队友写的还没太搞清楚，就先贴几题
hdu5948.Thickest Burger
模拟
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int T,a,b; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&a,&b); cout<<2*max(a,b)+min(a,b)<<endl; } return 0; } |
hdu5949.Relative atomic mass
模拟
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,ans; char str[200]; int main() { scanf("%d",&n); while(n--) { ans=0; scanf("%s",str); int len=strlen(str); for(int i=0;i<len;i++) if(str[i]=='H') ans++; else if(str[i]=='O') ans+=16; else ans+=12; cout<<ans<<endl; } return 0; } |
hdu5950.Recursive sequence
\(f_1=a,f_2=b,f_i=f_{i-2}*2+f_{i-1}+i^4\)，求\(f_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 59 60 61 62 63 64 65 66 67 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; const LL MOD=2147493647; int T,n,aa,bb; struct Matrix { int n,m; LL a[8][8]; Matrix() { n=m=0; memset(a,0,sizeof(a)); } }A,b; Matrix mul(const Matrix &p,const Matrix &q) { Matrix con; con.n=p.n,con.m=q.m; for(int i=1;i<=p.n;i++) for(int j=1;j<=q.m;j++) for(int k=1;k<=p.m;k++) con.a[i][j]=(con.a[i][j]+p.a[i][k]*q.a[k][j])%MOD; return con; } Matrix qpow(const Matrix &x,int n) { n--; Matrix p=x,con=x; while(n) { if(n&1) con=mul(con,p); p=mul(p,p); n>>=1; } return con; } int main() { A.n=7,A.m=7; A.a[1][1]=1,A.a[1][2]=2,A.a[1][3]=1; A.a[2][1]=1; A.a[3][3]=1,A.a[3][4]=4,A.a[3][5]=6,A.a[3][6]=4,A.a[3][7]=1; A.a[4][4]=1,A.a[4][5]=3,A.a[4][6]=3,A.a[4][7]=1; A.a[5][5]=1,A.a[5][6]=2,A.a[5][7]=1; A.a[6][6]=1,A.a[6][7]=1; A.a[7][7]=1; b.n=7,b.m=1; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&aa,&bb); b.a[1][1]=bb,b.a[2][1]=aa,b.a[3][1]=81,b.a[4][1]=27,b.a[5][1]=9,b.a[6][1]=3,b.a[7][1]=1; if(n==1) printf("%d\n",aa); else if(n==2) printf("%d\n",bb); else if(n==3) printf("%d\n",aa+aa+bb+81); else { b=mul(qpow(A,n-2),b); printf("%I64d\n",b.a[1][1]); } } return 0; } |
hdu5952.Counting Cliques
求一个无向图大小为S的团的数量
由于图的度数很小，选一个点，在其所有相邻点中取S-1个
复杂度\(C(20,10)*S^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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int 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 n,m,S,ans; int a[105],mp[105][105]; vector<int>e[105]; void dfs(int x,int K) { a[K]=x; if(K==S-1) { for(int i=0;i<e[x].size();i++) { int q=e[x][i];bool flag=1; for(int i=K-1;i>=1;i--) if(!mp[a[i]][q]){flag=0;break;} if(flag)ans++; } return; } for(int i=0;i<e[x].size();i++) { bool flag=1; for(int j=1;j<K;j++) if(!mp[a[j]][e[x][i]]){flag=0;break;} if(flag)dfs(e[x][i],K+1); } } int main() { T=read(); while(T--) { ans=0;memset(mp,0,sizeof(mp)); n=read(),m=read(),S=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); if(u<v)e[u].push_back(v); else e[v].push_back(u); mp[u][v]=mp[v][u]=1; } for(int i=1;i<=n;i++) dfs(i,1); cout<<ans<<endl; for(int i=1;i<=n;i++)e[i].clear(); } return 0; } |
hdu5954.The Elder
一棵树，长者在1号结点，记者从i号结点传递消息到1号结点，长度L的路程需要\(L^2\)的时间，不过他可以花P的时间停在某个结点让另一个记者接力
求最少需要时间，任意一个结点的记者都有方案把消息传递到1号结点
\(f_i=min\{f_j+(d_j-d_i)^2+P\}\)
斜率优化的式子，放到树上的时候，只要在某个结点记录一下决策序列的两个指针
同时记录右端有哪些元素被弹掉了，递归回来的时候恢复决策序列即可
|
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 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define N 100005 using namespace std; int read() { int 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,P,cnt; ll d[100005],f[100005]; struct data{ int to,next,v; }e[200005]; int last[100005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; } //slop>d_i double slop(int k,int j) { return (double)(f[j]-f[k]+d[j]*d[j]-d[k]*d[k])/(2*d[j]-2*d[k]); } int q[100005],l,r; void dfs(int x,int fa) { int tl=l,tr=r; while(l<r&&slop(q[l],q[l+1])<=d[x])l++; int t=q[l]; f[x]=min(d[x]*d[x],f[t]+(d[x]-d[t])*(d[x]-d[t])+P); vector<int>qtmp; while(l<r&&slop(q[r-1],q[r])>slop(q[r],x)) qtmp.push_back(q[r]),r--; q[++r]=x; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { d[e[i].to]=d[x]+e[i].v; dfs(e[i].to,x); } l=tl,r=tr; for(int i=0;i<qtmp.size();i++) q[tr-i]=qtmp[i]; } int main() { T=read(); while(T--) { memset(last,0,sizeof(last));cnt=0; l=1,r=0; n=read(),P=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } dfs(1,0); ll ans=0; for(int i=1;i<=n;i++) ans=max(ans,f[i]); cout<<ans<<endl; } return 0; } |
Subscribe
计数器 9302379
OI 课件=>
OI 课件=>