A BNU ACM校队时间安排表

大水题 开始把数字写错了，WA了一次

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define ll long long 7 using namespace std; 8  9 int main()10 {11     int cas, n;12     scanf("%d", &cas);13     while (cas--) {14         scanf("%d", &n);15         if (n==11||n==12) printf("Basic Training\n");16         if (n==12) printf("Rookie Contest\n");17         if (n==2||n==3||n==4) printf("Spring Training\n");18         if (n==4) printf("BNU Contest\n");19         if (n==7) printf("Practice Week\n");20         if (n==7||n==8) printf("Summer Training\n");21         if (n==9||n==10||n==11) printf("Regional Contest\n");22         if (n==1||n==5||n==6) printf("Unknown\n");23     }24     return 0;25 }
          
         
        
       
      

 

B 沙漠之旅

有N种油桶，每种无限桶，选4桶凑成L-X距离，判断能不能凑成。

bool dp[i][j]表示前i距离选了j桶。

if (dp[i][j]) dp[i+a[k]][j+1]=1;

k从1到N。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define ll long long 7 using namespace std; 8 bool dp[1001][4]; 9 int a[1001];10 int main()11 {12     int cas, l, x, n;13     scanf("%d", &cas);14     while (cas--) {15         scanf("%d%d%d", &l, &x, &n);16         l-=x;17         memset(dp, 0, sizeof(dp));18         dp[0][0]=1;19         for (int i=1; i<=n; i++)20             scanf("%d", &a[i]);21         for (int i=0; i<4; i++)22         for (int j=1; j<=n; j++) {23             for (int k=0; k+a[j]<=l; k++) {24                 if (dp[k][i])25                     dp[k+a[j]][i+1]=1;26             }27         }28         if (dp[l][4])29             printf("Yes\n");30         else31             printf("No\n");32     }33     return 0;34 }
          
         
        
       
      

 

C Adidas vs Adivon

给一张长和宽都是正整数的纸片，每次当前一方可以选择将纸片水平或竖直撕成相等的两半，扔掉一半。但是要求撕完后剩下的那部分纸片长和宽依旧是正整数。直到有一方不能再撕，该方即输掉这场博弈。

看长和宽能除以多少个2，加起来就是能撕的次数，如果次数是奇数是先手胜。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define ll long long 7 using namespace std; 8  9 int main()10 {11     int cas, n, m, ans;12     scanf("%d", &cas);13     while (cas--) {14         scanf("%d%d", &n, &m);15         ans=0;16         while(n%2==0) {17             ans++;18             n/=2;19         }20         while (m%2==0) {21             ans++;22             m/=2;23         }24         if (ans&1) printf("Adidas loses\n");25         else printf("Adivon prevails\n");26     }27     return 0;28 }
          
         
        
       
      

 

D 手速为王

给n个单词，每个单词翻转之后再次加入词典，一共就有2n个单词，每次输入一个单词的时候，都要把其他单词输进去，也就是输错2*n-1次，问总共按退格键的次数。

n<=1e5，n个单词的总长度<=1e5

最近软设写的太多，当时一直在想用链表。。

正解是trie树，记录每个节点的使用次数，就是有几个单词用到了这个节点，因为所有没用到这个节点的单词都要删这个节点，并且删除的次数是这个节点的使用次数，所以所有节点的（使用次数*没使用次数）之和就是总退格键数。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define ll long long 5 using namespace std; 6 const int maxn = 1000000; 7 int chd[maxn][26], tot; 8 int vis[maxn]; 9 void init()10 {11     tot=0;12     memset(vis, 0, sizeof(vis));13     memset(chd[0], 0, sizeof(chd[0]));14 }15 void Insert(char* s)16 {17     int cur=0, i;18     for (i=0; s[i]; i++) {19         if (!chd[cur][s[i]-'a']) {20             chd[cur][s[i]-'a']=++tot;21             memset(chd[tot], 0, sizeof(chd[tot]));22         }23         cur=chd[cur][s[i]-'a'];24         vis[cur]++;25     }26     cur=0;27     i--;28     for (; i>=0; i--) {29         if (!chd[cur][s[i]-'a']) {30             chd[cur][s[i]-'a']=++tot;31             memset(chd[tot], 0, sizeof(chd[tot]));32         }33         cur=chd[cur][s[i]-'a'];34         vis[cur]++;35     }36 }37 char s[100005];38 int main()39 {40     int cas, n;41     scanf("%d", &cas);42     while (cas--) {43         init();44         scanf("%d", &n);45         for (int i=0; i
        
       
      

 

F Taiko taiko

太鼓达人简化版，视连续n次击中为n连击，得分为1+2+...+n，例如序列YNNYYYNYN的总分为1+1+2+3+1=8，假设击中概率为P，对于长度为L的序列，求获得积分的期望。L<=1000，最多有1000组数据。

听说这题有规律惊讶

但是我是用DP做的。。

dp[i]表示长度为i的序列得分期望。

对于长度为i的序列，有两种情况，第i位为N，那么是dp[i-1]*q。

假如第i+1位为Y，那么是∑(dp[i-k-1]+sum[k])*p^k*q，也就是枚举最后有多长的连续的Y。sum[k]表示得分，∑sum[k]*p^k*q可以预处理出来。

假设f[i]=∑dp[i-k-1]*p^k*q，满足递推关系f[i]=f[i-1]*p+dp[i-1]*q。

总复杂度是O(n)

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define ll long long 7 using namespace std; 8 double sum[1005]; 9 double dp[1005];10 int main() {11     int cas;12     scanf("%d", &cas);13     int n;14     double p, tp, q;15     while (cas--) {16         scanf("%d%lf", &n, &p);17         tp=p; q=1-p;18         //sum[0]=p;19         for (int i=1; i<=n; i++) {20             sum[i]=sum[i-1]+i*(i+1)/2*tp;21             tp*=p;22         }23         dp[0]=0;24         tp=p;25         double ts=0;26         for (int i=1; i<=n; i++) {27             dp[i]=dp[i-1]*q+tp*i*(i+1)/2+sum[i-1]*q+ts*p;28             ts=ts*p+dp[i-1]*q;29             tp*=p;30         }31         printf("%lf\n", dp[n]);32     }33     return 0;34 }
          
         
        
       
      

 

H 硬币水题II

抛一个硬币，正面朝上的概率为p，反面朝上的概率为1-p。抛两次硬币一正一反称为一个决策，求平均要抛多少次，才能得到一个决策。

找规律。。发现答案就是1/(p*(1-p))

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define ll long long 7 using namespace std; 8 const int inf = 0x3f3f3f3f; 9 10 int main()11 {12     int cas;13     double p;14     scanf("%d", &cas);15     while (cas--) {16         scanf("%lf", &p);17         printf("%.2lf\n", 1/(p*(1-p)));18     }19     return 0;20 }
          
         
        
       
      

 

I 背包密码

背包密码系统加密过程如下：

选取一个长度为n的正整数超递增序列a[i]，满足a[1]<a[2]，a[1]+a[2]<a[3]，……，a[1]+a[2]+…+a[n-1]<a[n]。

选取正整数m>2*a[n]，w和m互质，v是w模m的逆，即(v*w)%m=1。b[i]=(w*a[i])%m。

加密时，对一段长为n的二进制串x[i]。有S= (b[1]*x[1]+b[2]*x[2]+…+b[n]*x[n])%m。

这种密码，告诉你b[i]就可以进行加密。但是仅有b[i]很难进行解密，因为需要求解一个普通的01背包问题 。只有再告诉你v和m，解密就会变得很简单，现在告诉你b[i]、v和m以及S，请你帮忙进行解密。

a数组有很好的性质，假如知道a[1]...a[n]的值和 a[1]*x[1]+a[2]*x[2]+…+a[n]*x[n]的值，就能直接求出x[1]...x[n]的值。

首先因为b[i]=(w*a[i])%m，所以a[i]≡b[i]*v，每次a[i]取最小值，也就是先让a[i]=b[i]*v%m，a[i]+=m，直到a[1]+a[2]+…+a[i-1]<a[i]

为什么是最小值呢？我也不知道。。只是某种直觉。。

把b[i]=w*a[i]%m带入到最后的式子中，得到S=w*(a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n])%m。

a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n]≡S*v，因为m>2*a[n]，a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n]肯定是小于m的。

所以a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n]=S*v%m

然后就能把x求出来了

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define ll long long 7 using namespace std; 8 int eular(int n) 9 {10     int ret=1,i;11     for (i=2;i*i<=n;i++)12         if (n%i==0)13         {14             n/=i,ret*=i-1;15             while (n%i==0)16                 n/=i,ret*=i;17         }18         if (n>1)19             ret*=n-1;20         return ret;    //n的欧拉数21 }22 ll pow_mod(ll a, int b)23 {24     if (b==0) return 1;25     ll ret=a, tmp=a;26     b--;27     while (b) {28         if (b&1) ret*=tmp;29         tmp*=tmp;30         b>>=1;31     }32     return ret;33 }34 ll b[35], a[35];35 int x[35];36 int main() {37     int cas;38     scanf("%d", &cas);39     int n;40     ll v, m, s;41     while (cas--) {42         scanf("%d", &n);43         for (int i=0; i
           
            =0; j--) {57 if (ans>=a[j]) {58 x[j]=1;59 ans-=a[j];60 }61 }62 //if (!ans) x[n-1]=1;63 for (int i=0; i
           
          
         
        
       
      

 

J 鸣人的查克拉

鸣人发明了一种忍术，可以在短时间内提高查克拉。

如果在某个时刻发动这个忍术，鸣人需要先消耗该时刻的查克拉值；在某个时候结束这个忍术，鸣人能获得该时刻的查克拉值（忍术必须先发动才能结束）。当然，如果某时刻鸣人具有的查克拉值少于该时刻的查克拉值，那么鸣人是不能发动该忍术的。

由于鸣人对这个忍术还不能很好地控制，所以他最多只能发动两次该忍术，并且两次忍术不能同时发动，也就是说必须结束一次忍术才能发动下一次（第一次结束时可以立即发动第二次）。

现在仪式已经做完了，鸣人知道了自己的查克拉的初始值，以及各个时刻的查克拉值，如果他最多可以发动两次该忍术（他也可以选择发动一次或者不发动），那么他最多能达到的查克拉值是多少？

预处理1-i的最小值，枚举第一次忍术结束的时间。这时候记录在某时刻之前发动一次忍术能得到的最大查克拉值。

从后往前再做一次，就能得到答案。

复杂度O(n)

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define ll long long 7 using namespace std; 8 const int inf = 0x3f3f3f3f; 9 int Min[10005], ans[10005], fmax[10005];10 int a[10005], amax[10005];11 int main()12 {13     int n, m, anss=0;14     scanf("%d%d", &n, &m);15     for (int i=1; i<=m; i++) {16         scanf("%d", &a[i]);17     }18     Min[0]=inf; fmax[m+1]=amax[0]=0;19     ans[0]=n;20     for (int i=1; i<=m; i++) {21         Min[i]=min(Min[i-1], a[i]);22         if (Min[i]<=n) {23             ans[i]=max(ans[i-1], n-Min[i]+a[i]);24             amax[i]=max(amax[i-1], ans[i]);25         }26         else27             amax[i]=amax[i-1];28     }29     anss=n;30     for (int i=m; i>=1; i--) {31         fmax[i]=max(fmax[i+1], a[i]);32         if (a[i]<=amax[i]) {33             anss=max(anss, amax[i]-a[i]+fmax[i]);34         }35     }36     printf("%d\n", anss);37     return 0;38 }
          
         
        
       
      

 

K PvZ once again

院子是N行M列的，而且种满了大蒜（耐久度K），coming的僵尸只有一只（然而这只僵尸貌似发生了变异，它每啃一口植物，同一列相同种类的植物也被啃掉一口），初始位置在第S行，求僵尸死在1-N号手推车的概率各是多少。

对于N=4的院子，有这么一个矩阵A，最后的概率就是A^(m*k)。

 

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #define ll long long 7 using namespace std; 8 const int inf = 0x3f3f3f3f; 9 double f[21][21], dp[21];10 struct Matrix11 {12     double mat[21][21];13     void clear() {14         for(int i=0; i<21; i++)15             for (int j=0; j<21; j++)16                 mat[i][j]=0;17     }18     friend void operator*=(Matrix &a, Matrix b)19     {20         Matrix ret;21         ret.clear();22         for (int i=0; i<21; i++)23         for (int j=0; j<21; j++) {24             for (int k=0; k<21; k++)25                 ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j];26         }27         a=ret;28     }29 }A, E, ans;30 Matrix pow_mod(Matrix a, int b)31 {32     if (b==0) return E;33     Matrix ret=a, tmp=a;34     b--;35     while (b) {36         if (b&1) ret*=tmp;37         tmp*=tmp;38         b>>=1;39     }40     return ret;41 }42 void view(Matrix x, int n)43 {44     for (int i=1; i<=n; i++){45         for (int j=1; j<=n; j++) printf("%lf ", x.mat[i][j]);46         puts("");47     }48     puts("");49 }50 int main()51 {52     int cas, n, m, k, s, f1, f2;53     scanf("%d", &cas);54     E.clear();55     for (int i=0; i<21; i++)56         E.mat[i][i]=1;57     while (cas--) {58         scanf("%d%d%d%d", &n, &m, &k, &s);59         if (n==1) {60             printf("1.0000\n");61             continue;62         }63         A.clear();64         for (int i=2; i
            
             1) {69 A.mat[1][2]=1;70 A.mat[n][n-1]=1;71 }72 //view(A, n);73 //view(pow_mod(A, 2), n);74 Matrix K;75 K=pow_mod(A, m*k);76 for (int i=1; i
            
           
          
         
        
       

 

L 斩

用直线切割一个矩形，求切割后的较小部分的面积。

讨论各种相交情况。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #define ll long long 7 using namespace std; 8  9 int main() {10     int cas;11     scanf("%d", &cas);12     double xl, yl, xr, yr, a, b, c;13     double y1, y2, x, x1, x2;14     while (cas--) {15         scanf("%lf%lf%lf%lf%lf%lf%lf", &xl, &yl, &xr, &yr, &a, &b, &c);16         if (a&&b) {17             y1=-(a*xl+c)/b;18             y2=-(a*xr+c)/b;19             if (y1>=yl&&y1<=yr) {20                 if (y2>=yl&&y2<=yr) {21                     printf("%.3lf\n", min((xr-xl)*(yr-yl)-(yr-y1+yr-y2)*(xr-xl)/2, (yr-y1+yr-y2)*(xr-xl)/2));22                 } else {23                     x=-(b*yr+c)/a;24                     if (x
            
             =yl&&y2<=yr) {33 x=-(b*yr+c)/a;34 if (x>xr) {35 x=-(b*yl+c)/a;36 printf("%.3lf\n", (y2-yl)*(xr-x)/2);37 } else {38 printf("%.3lf\n", (yr-y2)*(xr-x)/2);39 }40 } else {41 x1=-(b*yl+c)/a;42 x2=-(b*yr+c)/a;43 if (x1>=xl&&x1<=xr)44 if (x2>=xl&&x2<=xr)45 printf("%.3lf\n", min((xr-xl)*(yr-yl)-(xr-x1+xr-x2)*(yr-yl)/2, (xr-x1+xr-x2)*(yr-yl)/2));46 }47 }48 } else if (a) {49 x=-c/a;50 printf("%.3lf\n", min(x-xl, xr-x)*(yr-yl));51 } else if (b) {52 y1=-c/b;53 printf("%.3lf\n", min(y1-yl, yr-y1)*(xr-xl));54 }55 }56 return 0;57 }