2015 Multi-University Training Contest 2

题意：有块地为n*m列的矩阵，要建造矩形公寓来完全覆盖这块地((x,y)方格除外)

且每个公寓必须有一边在这块地的矩阵的边缘上。

求满足条件的方案中公寓最大面积的最小值。

思路：相当于用矩形填充n*m的矩阵，且矩形至少有一条边在该矩阵的边界上

若不考虑(x,y)方格被删除，ans=(min(m,n)+1)/2;

删除(x,y)后，若 m=n且n为奇数，且(x,y)在中心点，ans=ans-1;

否则 如图：

与(x,y)上下左右相邻点，只能往三个方向建公寓，对于这四个点

分别取对应的三个方向建公寓的最小面积s=min(s1,s2,s3);

ans=max(ans,s);

 1 #include<stdio.h>  2 #include<algorithm>  3 #define INF 999999999  4 const int dirX[4]={0,0,-1,1};  5 const int dirY[4]={1,-1,0,0};  6 using namespace std;  7 int main()  8 {  9     int n,m,x,y; 10     while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF){ 11         int ans=(min(m,n)+1)/2; 12         if(n%2&&m==n&&x==y&&x==(n+1)/2){ 13             printf("%d/n",ans-1); 14             continue; 15         } 16         for(int i=0;i<4;i++){ 17             int row=x+dirX[i]; 18             int col=y+dirY[i]; 19             int temp=INF; 20             if(row>=1&&row<=n&&col>=1&&col<=m){ 21                 if(row-1!=x) 22                     temp=min(temp,row); 23                 if(row+1!=x) 24                     temp=min(temp,n-row+1); 25                 if(col-1!=y) 26                     temp=min(temp,col); 27                 if(col+1!=y) 28                     temp=min(temp,m-col+1); 29                 ans=max(ans,temp); 30             } 31         } 32         printf("%d/n",ans); 33     } 34     return 0; 35 }

题意：一个环形道上有n个苹果树，第i棵树与仓库的顺时针距离为xi,树上有ai个苹果，仓库在位置0

你有一个容量为k的篮子，要从仓库出发去摘苹果，篮子装满后要回到起点清空篮子，

问你从起点出发，摘完所有苹果所走的最短路程。

思路：从起点可以顺时针或逆时针出发，最后的结果肯定是

顺时针取一定的苹果所走的最短路与逆时针走的最短路的和。

  1 #include<stdio.h>   2 #include<algorithm>   3 #include<string.h>   4 using namespace std;   5 struct node   6 {   7     long long dis,x;   8 } left[100001],right[100001];   9 long long pl[100001],pr[100001];  10 long long dpl[100001],dpr[100001];  11 int cmp(node x,node y)  12 {  13     return x.dis<y.dis;  14 }  15 int main()  16 {  17     int T;  18     int L,n,k;  19     long long sum;  20     long long ans;  21     scanf("%d",&T);  22     while(T--)  23     {  24         sum=0;  25         long long a,b;  26         int l=0,r=0;  27         scanf("%d%d%d",&L,&n,&k);  28         memset(pl,0,sizeof(pl));  29         memset(pr,0,sizeof(pr));  30         memset(dpl,0,sizeof(dpl));  31         memset(dpr,0,sizeof(dpr));  32         for(int i=0; i<n; i++)  33         {  34             scanf("%I64d%I64d",&a,&b);  35             if(a*2<=L)  36             {  37                 left[l].dis=a;  38                 left[l++].x=b;  39             }  40             else  41             {  42                 right[r].dis=L-a;  43                 right[r++].x=b;  44             }  45         }  46         sort(left,left+l,cmp);  47         sort(right,right+r,cmp);  48         for(int i=0; i<l; i++)  49         {  50             sum+=(left[i].dis)*(left[i].x/k)*2;  51             left[i].x=left[i].x%k;  52         }  53         for(int i=0; i<r; i++)  54         {  55             sum+=(right[i].dis)*(right[i].x/k)*2;  56             right[i].x=right[i].x%k;  57         }  58         //剩余的苹果离散化  59         int sl=1;//左边苹果总数  60         int sr=1;//右边苹果总数  61         for(int i=0; i<l; i++)  62         {  63             if(left[i].x)  64             {  65                 for(int j=0; j<left[i].x; j++)  66                 {  67                     pl[sl++]=left[i].dis;  68                 }  69             }  70         }  71         for(int i=0; i<r; i++)  72         {  73             if(right[i].x)  74             {  75                 for(int j=0; j<right[i].x; j++)  76                 {  77                     pr[sr++]=right[i].dis;  78                 }  79             }  80         }  81         for(int i = 1; i < sl; i++)  82         {  83             if(i<=k)  84                 dpl[i]=pl[i];  85             else  86                 dpl[i]=dpl[i-k]+pl[i];  87         }  88         for(int i = 1; i < sr; i++)  89         {  90             if(i<=k)  91                 dpr[i]=pr[i];  92             else  93                 dpr[i]=dpr[i-k]+pr[i];  94         }  95         ans=(dpl[sl-1]+dpr[sr-1])*2;//左边的往左边运，右边的网友边运  96         for(int i=0; i<=sl-1&&i<=k; i++)  97         {  98             int p1=sl-i-1;  99             int p2=max(0,sr-1-(k - i)); 100             if(2*(dpl[p1] + dpr[p2])+L<ans) 101                 ans=2*(dpl[p1] + dpr[p2])+L; 102         } 103         printf("%I64d/n",ans+sum); 104     } 105     return 0; 106 }

另一种方法更好理解：从起点可以顺时针或逆时针出发，最后的结果肯定是

顺时针取一定的苹果所走的最短路与逆时针走的最短路的和。

那么设dp[2][i]，0代表顺时针，1代表逆时针，i代表取的苹果数，

值为取完i个苹果回到原点的最短路程。x[i]为第i个苹果所在的位置。

以顺时针为例，如果2 x[i] <L，那么后来走的路程为2 x[i]，反之，为L；

转移方程：

dp[0][i] = min(dp[0][i],dp[0][i-j]+(2*x[i] <L ? 2*x[i] : L)) (1 <= j <= k)

因为dp[0][i]是非递减的,所以优化方程：

dp[0][i] = dp[0][i-k]+(2*x[i] <L ? 2*x[i] : L)

 1 #include<stdio.h>  2 #include<algorithm>  3 #define INF 0x3fffffffffffffff  4 const int N=100010;  5 using namespace std;  6 struct stu{  7     long long x,num;  8 }app[N];  9 long long L; 10 int n,k,sum; 11 long long dp[2][N]; 12 int cmp(stu a,stu b) 13 { 14     return a.x<b.x; 15 } 16 long long solve() 17 { 18     dp[0][0]=dp[1][0]=0; 19     int cnt=1; 20     for(int i=1;i<=n;i++){     //顺时针 21         for(int j=1;j<=app[i].num;j++){ 22             int t=cnt>k?cnt-k:0; 23             dp[0][cnt++]=dp[0][t]+min(app[i].x*2,L); 24         } 25     } 26     cnt=1; 27     for(int i=n;i>=1;i--){     //逆时针 28         for(int j=1;j<=app[i].num;j++){ 29             int t=cnt>k?cnt-k:0; 30             dp[1][cnt++]=dp[1][t]+min((L-app[i].x)*2,L); 31         } 32     } 33     long long ans=INF; 34     for(int i=0;i<=sum;i++) 35         ans=min(ans,dp[0][i]+dp[1][sum-i]); 36     return ans; 37 } 38 int main() 39 { 40     int T; 41     scanf("%d",&T); 42     while(T--){ 43         scanf("%I64d%d%d",&L,&n,&k); 44         sum=0; 45         for(int i=1;i<=n;i++){ 46             scanf("%I64d%I64d",&app[i].x,&app[i].num); 47             sum+=app[i].num; 48         } 49         sort(app+1,app+n+1,cmp); 50         long long ans=solve(); 51         printf("%I64d/n",ans); 52     } 53     return 0; 54 }

题意：有n个人，m组关系，表示谁和谁是朋友关系

朋友分为线上朋友和线下朋友，

求满足每个人的线上朋友数和线下朋友数相同

有多少种的情况

 1 #include<iostream>  2 #include<algorithm>  3 #include<stdio.h>  4 #include<string.h>  5 #include<stdlib.h>  6 using namespace std;  7 int n,m,sum;  8 struct node  9 { 10     int x,y; 11 } fri[100]; 12 int num[10]; 13 int lf[10]; 14 int rf[10]; 15 void dfs(int p) 16 { 17     if(p==m) 18     { 19         sum++; 20         return; 21     } 22     int x=fri[p].x; 23     int y=fri[p].y; 24     if(lf[x]&&lf[y]) 25     { 26         lf[x]--; 27         lf[y]--; 28         dfs(p+1); 29         lf[x]++; 30         lf[y]++; 31     } 32     if(rf[x]&&rf[y]) 33     { 34         rf[x]--; 35         rf[y]--; 36         dfs(p+1); 37         rf[x]++; 38         rf[y]++; 39     } 40 } 41 void work() 42 { 43     int flag=0; 44     for(int i=1; i<=n; i++) 45     { 46         lf[i]=num[i]/2; 47         rf[i]=num[i]/2; 48         if(num[i]%2) 49         { 50             flag=1; 51             break; 52         } 53     } 54     if(flag) 55     { 56         puts("0"); 57     } 58     else{ 59         dfs(0); 60         printf("%d/n",sum); 61     } 62 } 63 void input() 64 { 65     int a,b; 66     scanf("%d%d",&n,&m); 67     for(int i=0; i<m; i++) 68     { 69         scanf("%d%d",&a,&b); 70         fri[i].x=a; 71         fri[i].y=b; 72         num[a]++; 73         num[b]++; 74     } 75 } 76 int main() 77 { 78     int T; 79     scanf("%d",&T); 80     while(T--) 81     { 82         sum=0; 83         memset(num,0,sizeof(num)); 84         input(); 85         work(); 86     } 87     return 0; 88 }

  1 #include<stdio.h>   2 int main()   3 {   4     int N;   5     while(scanf("%d",&N)!=EOF)   6     {   7         if(N<=3)   8             printf("-1/n");   9         else if (N == 4)  10         {  11             printf("1 * 2/n5 + 3/n6 + 4/n");  12         }  13         else if(N == 5)  14         {  15             printf("1 / 2/n");  16             printf("6 / 3/n");  17             printf("4 - 7/n");  18             printf("5 * 8/n");  19         }  20         else if(N==6)  21         {  22             printf("1 + 2/n");  23             printf("3 + 7/n");  24             printf("4 + 8/n");  25             printf("9 // 5/n");  26             printf("10 * 6/n");  27         }  28         else if(N == 7)  29         {  30             printf("1 + 2/n");  31             printf("3 + 8/n");  32             printf("9 / 4/n");  33             printf("5 / 6/n");  34             printf("11 + 7/n");  35             printf("10 * 12/n");  36         }  37         else if(N == 8)  38         {  39             printf("1 + 2/n");  40             printf("3 + 9/n");  41             printf("4 - 5/n");  42             printf("11 * 6/n");  43             printf("12 * 7/n");  44             printf("13 * 8/n");  45             printf("10 + 14/n");  46         }  47         else if(N == 9)  48         {  49             printf("1 + 2/n");  50             printf("3 + 4/n");  51             printf("11 + 5/n");  52             printf("12 + 6/n");  53             printf("13 + 7/n");  54             printf("14 + 8/n");  55             printf("15 / 9/n");  56             printf("10 + 16/n");  57         }  58         else if(N == 10)  59         {  60             printf("1 + 2/n");  61             printf("11 / 3/n");  62             printf("4 + 12/n");  63             printf("6 + 5/n");  64             printf("14 + 7/n");  65             printf("8 + 15/n");  66             printf("9 + 10/n");  67             printf("16 / 17/n");  68             printf("13 * 18/n");  69         }  70         else if(N == 11)  71         {  72             printf("1 + 2/n");  73             printf("12 / 3/n");  74             printf("4 / 5/n");  75             printf("6 + 14/n");  76             printf("7 - 8/n");  77             printf("16 * 9/n");  78             printf("17 * 10/n");  79             printf("18 * 11/n");  80             printf("13 * 15/n");  81             printf("20 + 19/n");  82         }  83         else if(N == 12)  84         {  85             printf("1 + 2/n");  86             printf("3 - 4/n");  87             printf("14 * 5/n");  88             printf("6 * 15/n");  89             printf("7 * 16/n");  90             printf("8 * 17/n");  91             printf("9 * 18/n");  92             printf("10 * 19/n");  93             printf("11 * 20/n");  94             printf("12 * 21/n");  95             printf("13 + 22/n");  96         }  97         else  98         {  99             if(N%2==0) 100             { 101                 printf("1 + 2/n"); 102                 int p=3,q=N+1; 103                 for(int i=1; i<3; i++) 104                 { 105                     printf("%d + %d/n",p++,q++); 106                 }//加三次N 107                 printf("%d / %d/n",q++,p++);//除以N得到4 108                 printf("%d + %d/n",p,p+1);//得到2倍的N 109                 int cnt1=q++; 110                 p+=2; 111                 for (int i=1; i<5; i++) 112                 { 113                     printf("%d + %d/n",p++,q++); 114                 }//得到6倍的N 115                 printf("%d / %d/n",q++,p++);//得到6 116                 int cnt2=q++; 117                 while (p<N) 118                 { 119                     printf("%d / %d/n",p,p+1);//得到0 120                     p+=2; 121                     q++; 122                     printf("%d * %d/n",q-1,cnt1); 123                     cnt1=q++; 124                 } 125                 printf("%d * %d/n",cnt1,cnt2);//4*6=24 126             } 127             else 128             { 129                 printf("1 + 2/n"); 130                 int p=3,q=N+1; 131                 for (int i=1; i<2; i++) 132                 { 133                     printf("%d + %d/n",p++,q++); 134                 } 135                 printf("%d / %d/n",q++,p++);//得到3 136                 printf("%d + %d/n",p,p+1); 137                 int cnt1=q++; 138                 p+=2; 139                 for (int i=1; i<7; i++) 140                 { 141                     printf("%d + %d/n",p++,q++); 142                 } 143                 printf("%d / %d/n",q++,p++);//得到8 144                 int cnt2=q++; 145                 while (p<N) 146                 { 147                     printf("%d / %d/n",p,p+1); 148                     p+=2; 149                     q++; 150                     printf("%d * %d/n",q-1,cnt1); 151                     cnt1=q++; 152                 } 153                 printf("%d * %d/n",cnt1,cnt2);//3*8=24 154             } 155         } 156     } 157     return 0; 158 }