17-06-14模拟赛

T1:

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define MN 100005
 5 using namespace std;
 6 inline int in(){
 7     int x=0;bool f=0; char c;
 8     for (;(c=getchar())<'0'||c>'9';f=c=='-');
 9     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
10     return f?-x:x;
11 }
12 struct edge{
13     int to,next;
14 }e[MN];
15 int head[MN],edi[MN],t[MN],x[MN],cnt=0,n,tail=0,cur;
16 char op[MN];
17 inline void ins(int x,int y){
18     e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
19 }
20 void dfs(int p){
21     if (op[p]=='T') t[++tail]=x[p];
22     if (op[p]=='Q') x[p]=t[x[p]];
23     for (int i=head[p];i;i=e[i].next) dfs(e[i].to);
24     if (op[p]=='T') --tail;
25 }
26 int main()
27 {
28     n=in();cur=0;for (int i=1;i<=n;++i){
29         do op[i]=getchar();while (op[i]!='T'&&op[i]!='U'&&op[i]!='Q');
30         if (op[i]=='T') getchar(),x[i]=getchar();else x[i]=in();
31         if (op[i]=='U') ins(edi[cur-x[i]],i);else ins(i-1,i);
32         if (op[i]=='T'||op[i]=='U') edi[++cur]=i;
33     }dfs(0);
34     for (int i=1;i<=n;++i) if (op[i]=='Q') printf("%c
",(char)x[i]);return 0;
35 }

T2:动态规划。考虑将1-n从小到大插入数列。

设f[i][j]表示数列中已插入1-i,恰有j个"<"的方案数，则f[i][j]=f[i-1][j-1]*(i-j)+f[i-1][j]*(j+1).

Code:

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #define MOD 2012 
 8 using namespace std;
 9 inline int in(){
10     int x=0;bool f=0; char c;
11     for (;(c=getchar())<'0'||c>'9';f=c=='-');
12     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
13     return f?-x:x;
14 }int f[1003][1003],n,k;
15 int main()
16 {
17     n=in();k=in();
18     for (int i=1;i<=n;++i) f[i][0]=f[i][i-1]=1;
19     for (int i=2;i<=n;++i)
20     for (int j=1;j<=min(k,i-1);++j)
21     f[i][j]=(f[i-1][j]*(j+1)%MOD+f[i-1][j-1]*(i-j)%MOD)%MOD;
22     printf("%d",f[n][k]);return 0;
23 }

T3:

考虑从后往前处理，可以发现是否开采或维修只对在其后星球的开采收入产生影响，即其后星球的最优方案与是否在该星球开采或修复无关。所以可以贪心处理本题。

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define MN 100005
 5 using namespace std;
 6 inline int in(){
 7     int x=0;bool f=0; char c;
 8     for (;(c=getchar())<'0'||c>'9';f=c=='-');
 9     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
10     return f?-x:x;
11 }
12 int n,w,x[MN];
13 double k,c,ans;
14 bool tp[MN];
15 int main()
16 {
17     n=in();k=1-(in()/100.0);c=1+(in()/100.0);w=in();
18     for (int i=1;i<=n;++i) tp[i]=in()-1,x[i]=in();ans=0.0;
19     for (int i=n;i;--i){
20         if (!tp[i]) ans=max(ans,ans*k+x[i]);
21         else ans=max(ans,ans*c-x[i]);
22     }printf("%.2lf",ans*w);
23     return 0;
24 }