Minieye杯第十五届华中科技大学程序设计邀请赛网络赛 部分题目
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
D Grid
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=2e2+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 char s[maxn][maxn]; 20 21 int main() 22 { 23 int h,w,n,m,i,j,x,y; 24 scanf("%d%d%d",&h,&w,&n); 25 m=(h*w+1)/2; 26 if (n>m) 27 printf("-1"); 28 else 29 { 30 for (i=0;i<h;i++) 31 for (j=0;j<w;j++) 32 s[i][j]='*'; 33 x=0,y=0; 34 while (n--) 35 { 36 s[x][y]='#'; 37 y+=2; 38 if (y>=w) 39 { 40 x++; 41 if (s[x-1][0]=='#') 42 y=1; 43 else 44 y=0; 45 } 46 } 47 for (i=0;i<h;i++) 48 { 49 for (j=0;j<w;j++) 50 printf("%c",s[i][j]); 51 printf("\n"); 52 } 53 } 54 return 0; 55 } 56 /* 57 58 */
G Multithread
模拟
inf long long
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e6+10; 16 const ll inf=1e18; 17 const double eps=1e-15; 18 19 ll a[maxn],c[maxn],t=0; 20 21 int main() 22 { 23 int n,i,j; 24 double z; 25 scanf("%d",&n); 26 for (i=1;i<=n;i++) 27 scanf("%lld",&a[i]); 28 sort(a+1,a+n+1); 29 a[n+1]=inf; 30 j=1; 31 for (i=1;i<=n;i++) 32 { 33 while (a[j]==a[i]) 34 j++; 35 c[i]=a[j]; 36 } 37 for (i=1;i<=n;i++) 38 { 39 t=max(t,a[i]); 40 if (t>=c[i]) 41 { 42 printf("0"); 43 return 0; 44 } 45 t+=ceil(sqrt(a[i])); 46 } 47 printf("1"); 48 return 0; 49 } 50 /* 51 4 52 10 11 17 18 53 54 4 55 10 11 18 18 24 56 57 5 58 0 0 0 3 4 59 60 10 61 1000000000 1000000000 1000000000 1000000000 1000000000 62 1000000000 1000000000 1000000000 1000000000 1000000000 63 */
I Tree
贪心，一颗子树的权值和大于某个值则使用该子树，否则该子树必定被子树根的父亲使用。
其实上界可以为sum(c[i])/k，但二分，也节省不了几次操作。
注意long long，莫名其妙地使用“ll*”失效了，所以我输入的变量的类型设置为long long。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e5+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 struct node 20 { 21 int d; 22 node *to; 23 }*e[maxn]; 24 25 ll c[maxn],sum[maxn],m; 26 bool vis[maxn]; 27 int g=0; 28 29 void dfs(int d) 30 { 31 vis[d]=1; 32 node *p=e[d]; 33 sum[d]+=c[d]; 34 while (p) 35 { 36 if (!vis[p->d]) 37 { 38 dfs(p->d); 39 sum[d]+=sum[p->d]; 40 } 41 p=p->to; 42 } 43 if (sum[d]>=m) 44 g++,sum[d]=0; 45 } 46 47 int main() 48 { 49 node *p; 50 int x,y,i; 51 ll n,k,l,r; 52 scanf("%lld%lld",&n,&k); 53 for (i=1;i<n;i++) 54 { 55 scanf("%d%d",&x,&y); 56 p=new node(); 57 p->d=y; 58 p->to=e[x]; 59 e[x]=p; 60 61 p=new node(); 62 p->d=x; 63 p->to=e[y]; 64 e[y]=p; 65 } 66 for (i=1;i<=n;i++) 67 scanf("%lld",&c[i]); 68 l=1,r=100000*n/k; 69 while (l<=r) 70 { 71 m=(l+r)>>1; 72 g=0; 73 memset(vis,0,sizeof(vis)); 74 memset(sum,0,sizeof(sum)); 75 dfs(1); 76 if (g>=k) 77 l=m+1; 78 else 79 r=m-1; 80 } 81 printf("%lld",r); 82 return 0; 83 } 84 /* 85 5 5 86 1 2 87 1 3 88 2 4 89 2 5 90 4 4 3 4 5 91 */
K Car
注意x，y的作用域，减少了不少方案。
还是那样，想清楚了再编码，验证一下测试样例，造多几个数据。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e6+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 ll f[maxn][2]; 20 21 int main() 22 { 23 char ch; 24 ll a,b,c,d,x=0,y=0,sum=0,v=1<<30; 25 int n,i; 26 bool vis=0; 27 scanf("%d",&n); 28 for (i=1;i<=n;i++) 29 { 30 scanf("\n%c",&ch); 31 if (ch=='C') 32 { 33 scanf("%lld%lld%lld%lld",&a,&b,&c,&d); 34 sum+=(y+b)*v*2; 35 sum-=b*(v-(x+a)); 36 x+=a-c; 37 y+=b-d; 38 sum-=d*(x+v); 39 vis=1; 40 } 41 else 42 { 43 scanf("%lld%lld",&a,&b); 44 if (!vis) 45 { 46 if (i&1) 47 x+=a; 48 else 49 x-=a; 50 sum-=(v-x)*b; 51 y+=b; 52 } 53 else 54 { 55 if (i&1) 56 x-=a; 57 else 58 x+=a; 59 sum-=(x+v)*b; 60 y-=b; 61 } 62 } 63 } 64 printf("%lld",sum); 65 return 0; 66 } 67 /* 68 4 69 C 10 10 15 3 70 B 2 5 71 A 3 1 72 B 6 1 73 74 4 75 C 10 10 15 20 76 A 10 2 77 B 6 3 78 A 1 5 79 80 3 81 B 100 60 82 A 30 10 83 C 50 200 120 30 84 85 4 86 A 100 60 87 B 30 50 88 C 90 700 170 800 89 B 10 10 90 */
J Another Easy Problem
比赛时暴力了一发，感觉数值在[1,50]范围内，结果不会太大。看了一下数据，果然，结果<=5，但时间上仍然承受不了。
方法比较巧妙。其实这种题，要养成往dp想的习惯。。。
dp,差值可以选择用绝对值表示，因为sum(a[i])<=5000,所以途中，差值最多不超过2500，否则无法再‘’追‘’回来，使差值为0。而数组的第一维，可以使用滚动数组，数组的第二维，其实最多可以开到2500+50即可。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e2+10; 16 const int maxm=5e3+10; 17 const int inf=1e9; 18 const double eps=1e-8; 19 20 int f[maxn][maxm]; 21 22 int main() 23 { 24 int t,n,a,i,j; 25 scanf("%d",&t); 26 while (t--) 27 { 28 memset(f,0x3f,sizeof(f)); 29 f[0][0]=0; 30 scanf("%d",&n); 31 for (i=1;i<=n;i++) 32 { 33 scanf("%d",&a); 34 for (j=0;j<=2500;j++) 35 f[i][j]=min(f[i-1][j]+1,min(f[i-1][j+a],f[i-1][abs(j-a)])); 36 } 37 printf("%d\n",f[n][0]); 38 } 39 return 0; 40 } 41 /* 42 5 43 1 2 4 8 16 44 45 5 46 1 10 11 30 49 47 */
B Balls
比赛时考虑到与数学推导有关，没仔细想。
比赛时应该打表找规律的。哎，其它题写太卡了，耗费大量时间。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e4+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 ll sum=0; 19 20 void dfs(int k,int s,ll v) 21 { 22 if (k==0) 23 // { 24 // printf("%lld ",v); 25 sum+=v; 26 // } 27 28 else 29 { 30 for (int i=s-k+1;i>=1;i--) 31 dfs(k-1,s-i,v*i); 32 } 33 } 34 35 int main() 36 { 37 int k,s; 38 // scanf("%d%d",&k,&s); 39 for (k=1;k<=10;k++) 40 for (s=1;s<=10;s++) 41 { 42 sum=0; 43 dfs(k,s,1); 44 printf("%4lld",sum); 45 if (s==10) 46 printf("\n"); 47 else 48 printf(" "); 49 } 50 return 0; 51 } 52 /* 53 54 */
如果不熟悉，再打一个组合数学的表。
方法挺巧妙的！组合数学。
lucas,直接求逆超时了，求逆初始化，参见代码。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=5e6+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 ll p,mul[maxn],chu[maxn]; 20 21 ll pow(ll a,ll b) 22 { 23 ll y=1; 24 while (b) 25 { 26 if (b & 1) 27 y=y*a%p; 28 a=a*a%p; 29 b>>=1; 30 } 31 return y; 32 } 33 34 ll cal(ll n,ll m) 35 { 36 if (n<m) 37 return 0; 38 ll y=1,i; 39 if (m+m>n) 40 m=n-m; 41 return mul[n]*chu[n-m]%p*chu[m]%p; 42 // for (i=1;i<=m;i++) 43 // y=y*(n+1-i)%p*pow(i,p-2)%p; 44 return y; 45 } 46 47 int main() 48 { 49 ll n,m,r,i; 50 scanf("%lld%lld%lld",&m,&n,&p); 51 ///init 52 mul[0]=1; 53 for (i=1;i<p;i++) 54 mul[i]=mul[i-1]*i%p; 55 chu[p-1]=pow(mul[p-1],p-2); 56 for (i=p-2;i>=1;i--) 57 chu[i]=chu[i+1]*(i+1)%p; 58 59 n+=m,m*=2; 60 r=1; 61 while (m) 62 { 63 r=r*cal(n%p,m%p)%p; 64 n/=p,m/=p; 65 } 66 printf("%lld",r); 67 return 0; 68 } 69 /* 70 71 */
E Lolita Dress
组合公式变形
\( \begin{equation*}\begin{split}&\sum_{n=1}^{min(x,y)}(C_{x}^{n-1}*C_{y}^{n}) \\&=\sum_{n=1}^{min(x,y)}(C_{x}^{x-n+1}*C_{y}^{n}) \\&=C_{x+y}^{x+1}\end{split}\end{equation*} \)
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e6+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 const ll mod=1e9+7; 19 20 int a[maxn]; 21 ll mul[maxn],chu[maxn]; 22 23 ll pow(ll a,ll b) 24 { 25 ll y=1; 26 while (b) 27 { 28 if (b&1) 29 y=y*a%mod; 30 a=a*a%mod; 31 b>>=1; 32 } 33 return y; 34 } 35 36 ll cal(ll x,ll y) 37 { 38 return mul[x]*chu[y]%mod*chu[x-y]%mod; 39 } 40 41 int main() 42 { 43 ll sum=0; 44 int n,x=0,y=0,i; 45 scanf("%d",&n); 46 mul[0]=1; 47 for (i=1;i<=n;i++) 48 mul[i]=mul[i-1]*i%mod; 49 chu[n]=pow(mul[n],mod-2); 50 for (i=n-1;i>=0;i--) 51 chu[i]=chu[i+1]*(i+1)%mod; 52 53 for (i=1;i<=n;i++) 54 { 55 scanf("%d",&a[i]); 56 if (a[i]) 57 y++; 58 } 59 for (i=1;i<=n;i++) 60 if (a[i]==0) 61 { 62 sum=(sum+cal(x+y,x+1))%mod; 63 x++; 64 } 65 else 66 y--; 67 printf("%lld",sum); 68 return 0; 69 } 70 /* 71 72 */
A Wormhole Construction
之前理解错题意了，只需要求最小的d，不需要最佳的方案(最小边)
打表找规律
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=20; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 int n,r; 20 21 struct node 22 { 23 int a[maxn][maxn]; 24 node() 25 { 26 int i,j; 27 for (i=1;i<=n;i++) 28 for (j=1;j<=n;j++) 29 a[i][j]=0; 30 } 31 node operator*(node y) 32 { 33 node z=*this; 34 int i,j,k; 35 for (k=1;k<=n;k++) 36 for (i=1;i<=n;i++) 37 for (j=1;j<=n;j++) 38 z.a[i][j]|=a[i][k]*y.a[k][j]; 39 return z; 40 } 41 int work() 42 { 43 node z; 44 int i,j,l; 45 z=*this; 46 for (l=1;l<n;l++) 47 { 48 z=z*(*this); 49 j=1; 50 for (i=1;i<=n;) 51 { 52 if (i!=j && z.a[i][j]==0) 53 break; 54 if (j==n) 55 i++,j=1; 56 else 57 j++; 58 } 59 if (i==n+1) 60 return l; 61 } 62 return n; 63 } 64 }mat,result; 65 66 void build(int i,int j) 67 { 68 int k,v; 69 ///guess, fasten the speed 70 // if (r==2) 71 // return; 72 for (k=1;k>=0;k--) 73 { 74 if (k==1 && (i==j || mat.a[j][i]==1)) 75 continue; 76 mat.a[i][j]=k; 77 if (j==n) 78 { 79 if (i==n) 80 { 81 v=mat.work()+1; 82 ///observe 83 if (n>=5 && v==2) 84 { 85 for (int u=1;u<=n;u++) 86 { 87 for (int v=1;v<=n;v++) 88 printf("%d ",mat.a[u][v]); 89 printf("\n"); 90 } 91 printf("\n"); 92 } 93 if (v<r) 94 { 95 r=v; 96 result=mat; 97 } 98 99 return; 100 } 101 build(i+1,1); 102 } 103 else 104 build(i,j+1); 105 } 106 } 107 108 int main() 109 { 110 for (n=3;n<=10;n++) 111 { 112 r=n; 113 build(1,1); 114 printf("%d : %d\n",n,r); 115 // for (int i=1;i<=n;i++) 116 // { 117 // for (int j=1;j<=n;j++) 118 // printf("%d ",result.a[i][j]); 119 // printf("\n"); 120 // } 121 } 122 return 0; 123 } 124 /* 125 3 : 2 126 0 1 0 127 0 0 1 128 1 0 0 129 4 : 3 130 0 1 1 0 131 0 0 1 1 132 0 0 0 1 133 1 0 0 0 134 5 : 2 135 0 1 1 1 0 136 0 0 1 0 1 137 0 0 0 1 1 138 0 1 0 0 1 139 1 0 0 0 0 140 6 : 2 141 0 1 1 1 0 0 142 0 0 1 1 1 0 143 0 0 0 1 0 1 144 0 0 0 0 1 1 145 1 0 1 0 0 1 146 1 1 0 0 0 0 147 7 : 2 148 0 1 1 1 1 1 0 149 0 0 1 1 1 0 1 150 0 0 0 1 0 1 1 151 0 0 0 0 1 1 1 152 0 0 1 0 0 1 1 153 0 1 0 0 0 0 1 154 1 0 0 0 0 0 0 155 7 several minutes 156 */
就能发现除了4之外，其它的答案都是2。
就能发现两个比较有意思的解法(当然，这是在已经答案的基础上，尴尬。。。)
0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e4+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 20 21 int main() 22 { 23 int n,m,i,j,k; 24 scanf("%d",&n); 25 if (n==4) 26 { 27 printf("3 4\n1 2\n2 3\n3 4\n4 1"); 28 return 0; 29 } 30 31 if (n&1) 32 { 33 m=n>>1; 34 printf("2 %d\n",n*m); 35 for (i=1;i<=n;i++) 36 for (j=1;j<=m;j++) 37 { 38 k=i+j; 39 if (k>n) 40 k-=n; 41 printf("%d %d\n",i,k); 42 } 43 } 44 else 45 { 46 m=(n-1)>>1; 47 printf("2 %d\n",(n-1)*m+4); 48 for (i=2;i<=n;i++) 49 for (j=1;j<=m;j++) 50 { 51 k=i+j; 52 if (k>n) 53 k-=n-1; 54 printf("%d %d\n",i,k); 55 } 56 printf("%d %d\n",1,2); 57 printf("%d %d\n",1,2+m+1); 58 printf("%d %d\n",3,1); 59 printf("%d %d\n",3+m+1,1); 60 } 61 return 0; 62 } 63 /* 64 65 */
不对///标程中的cnt，满足条件的区间[x,y]，x in [L,i], y in [i,R]。
更多精彩
