浙江理工大学2019年5月赛

xiaoxiao2023-11-07 160

Problem A 24点

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=0

补题地址：http://47.96.116.66/problem.php?id=2110

题意：

题解：

按题意模拟即可

用next_permutation()枚举数字的所有排列情况

对于某种排列，用四进制枚举出运算符的所有情况

最后再枚举括号的情况

C++版本一

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int a[5]; char str; struct node{}; bool check(){ int A=a[1]; int B=a[2]; int C=a[3]; int D=a[4]; if(A+B+C+D==24)return 1; if(A+B+C-D==24)return 1; if(A+B+C*D==24)return 1; if(A+(B+C)*D==24)return 1; if((A+B+C)*D==24)return 1; if(A+B+C/D==24&&1.0*C/D==C/D)return 1; if(A+(B+C)/D==24&&1.0*(B+C)/D==(B+C)/D)return 1; if((A+B+C)/D==24&&1.0*(A+B+C)/D==(A+B+C)/D)return 1; if(A+B-C+D==24)return 1; if(A+B-C-D==24)return 1; if(A+B-C*D==24)return 1; if(A+(B-C)*D==24)return 1; if((A+B-C)*D==24)return 1; if(A+B-C/D==24&&1.0*C/D==C/D)return 1; if(A+(B-C)/D==24&&1.0*(B-C)/D==(B-C)/D)return 1; if((A+B-C)/D==24&&1.0*(A+B-C)/D==(A+B-C)/D)return 1; if(A+B*C+D==24)return 1; if((A+B)*C+D==24)return 1; if(A+B*(C+D)==24)return 1; if((A+B)*(C+D)==24)return 1; if(A+B*C-D==24)return 1; if((A+B)*C-D==24)return 1; if(A+B*(C-D)==24)return 1; if((A+B)*(C-D)==24)return 1; if(A+B*C*D==24)return 1; if((A+B)*C*D==24)return 1; if(A+B*C/D==24&&1.0*B*C/D==B*C/D)return 1; if((A+B)*C/D==24&&1.0*(A+B)*C/D==(A+B)*C/D)return 1; if((A+B*C)/D==24&&1.0*(A+B*C)/D==(A+B*C)/D)return 1; if(A+B/C+D==24&&1.0*B/C==B/C)return 1; if((A+B)/C+D==24&&1.0*(A+B)/C==(A+B)/C)return 1; if(A+B/(C+D)==24&&1.0*B/(C+D)==B/(C+D))return 1; if((A+B)/(C+D)==24&&1.0*(A+B)/(C+D)==(A+B)/(C+D))return 1; if(A+B/C-D==24&&1.0*B/C==B/C)return 1; if((A+B)/C-D==24&&1.0*(A+B)/C==(A+B)/C)return 1; if(C-D!=0&&A+B/(C-D)==24&&1.0*B/(C-D)==B/(C-D))return 1; if(C-D!=0&&(A+B)/(C-D)==24&&1.0*(A+B)/(C-D)==(A+B)/(C-D))return 1; if(A+B/C*D==24&&1.0*B/C*D==B/C*D)return 1; if((A+B)/C*D==24&&1.0*(A+B)/C*D==(A+B)/C*D)return 1; if(A+B/C/D==24&&1.0*B/C/D==B/C/D)return 1; if((A+B)/C/D==24&&1.0*(A+B)/C/D==(A+B)/C/D)return 1; if(A-B+C+D==24)return 1; if(A-B+C-D==24)return 1; if(A-B+C*D==24)return 1; if(A-(B+C)*D==24)return 1; if((A-B+C)*D==24)return 1; if(A-B+C/D==24&&1.0*C/D==C/D)return 1; if(A-(B+C)/D==24&&1.0*(B+C)/D==(B+C)/D)return 1; if((A-B+C)/D==24&&1.0*(A-B+C)/D==(A-B+C)/D)return 1; if(A-B-C+D==24)return 1; if(A-B-C-D==24)return 1; if(A-B-C*D==24)return 1; if(A-(B-C)*D==24)return 1; if((A-B-C)*D==24)return 1; if(A-B-C/D==24&&1.0*C/D==C/D)return 1; if(A-(B-C)/D==24&&1.0*(B-C)/D==(B-C)/D)return 1; if((A-B-C)/D==24&&1.0*(A-B-C)/D==(A-B-C)/D)return 1; if(A-B*C+D==24)return 1; if((A-B)*C+D==24)return 1; if(A-B*(C+D)==24)return 1; if((A-B)*(C+D)==24)return 1; if(A-B*C-D==24)return 1; if((A-B)*C-D==24)return 1; if(A-B*(C-D)==24)return 1; if((A-B)*(C-D)==24)return 1; if(A-B*C*D==24)return 1; if((A-B)*C*D==24)return 1; if(A-B*C/D==24&&1.0*C/D==C/D)return 1; if((A-B)*C/D==24&&1.0*(A-B)*C/D==(A-B)*C/D)return 1; if((A-B*C)/D==24&&1.0*(A-B*C)/D==(A-B*C)/D)return 1; if(A-B/C+D==24&&1.0*B/C==B/C)return 1; if((A-B)/C+D==24&&1.0*(A-B)/C==(A-B)/C)return 1; if(A-B/(C+D)==24&&1.0*B/(C+D)==B/(C+D))return 1; if((A-B)/(C+D)==24&&1.0*(A-B)/(C+D)==(A-B)/(C+D))return 1; if(A-B/C-D==24&&1.0*B/C==B/C)return 1; if((A-B)/C-D==24&&1.0*(A-B)/C==(A-B)/C)return 1; if(C-D!=0&&A-B/(C-D)==24&&1.0*B/(C-D)==B/(C-D))return 1; if(C-D!=0&&(A-B)/(C-D)==24&&1.0*(A-B)/(C-D)==(A-B)/(C-D))return 1; if(A-B/C*D==24&&1.0*B/C*D==B/C*D)return 1; if((A-B)/C*D==24&&1.0*(A-B)/C*D==(A-B)/C*D)return 1; if(A-B/C/D==24&&1.0*B/C/D==B/C/D)return 1; if((A-B)/C*D==24&&1.0*(A-B)/C*D==(A-B)/C*D)return 1; if(A*B+C+D==24)return 1; if(A*(B+C)+D==24)return 1; if(A*(B+C+D)==24)return 1; if(A*B+C-D==24)return 1; if(A*(B+C)-D==24)return 1; if(A*(B+C-D)==24)return 1; if(A*B+C*D==24)return 1; if(A*(B+C)*D==24)return 1; if(A*(B+C*D)==24)return 1; if((A*B+C)*D==24)return 1; if(A*B+C/D==24&&1.0*C/D==C/D)return 1; if(A*(B+C)/D==24&&1.0*A*(B+C)/D==A*(B+C)/D)return 1; if(A*(B+C/D)==24&&1.0*C/D==C/D)return 1; if((A*B+C)/D==24&&1.0*(A*B+C)/D==(A*B+C)/D)return 1; if(A*B-C+D==24)return 1; if(A*(B-C)+D==24)return 1; if(A*(B-C+D)==24)return 1; if(A*B-C-D==24)return 1; if(A*(B-C)-D==24)return 1; if(A*(B-C-D)==24)return 1; if(A*B-C*D==24)return 1; if(A*(B-C)*D==24)return 1; if(A*(B-C*D)==24)return 1; if((A*B-C)*D==24)return 1; if(A*B-C/D==24&&1.0*C/D==C/D)return 1; if(A*(B-C)/D==24&&1.0*A*(B-C)/D==A*(B-C)/D)return 1; if(A*(B-C/D)==24&&1.0*C/D==C/D)return 1; if((A*B-C)/D==24&&1.0*(A*B-C)/D==(A*B-C)/D)return 1; if(A*B*C+D==24)return 1; if(A*B*(C+D)==24)return 1; if(A*B*C-D==24)return 1; if(A*B*(C-D)==24)return 1; if(A*B*C*D==24)return 1; if(A*B*C/D==24&&1.0*A*B*C/D==A*B*C/D)return 1; if(A*B/C+D==24&&1.0*A*B/C==A*B/C)return 1; if(A*B/(C+D)==24&&1.0*A*B/(C+D)==A*B/(C+D))return 1; if(A*B/C-D==24&&1.0*A*B/C==A*B/C)return 1; if(C-D!=0&&A*B/(C-D)==24&&1.0*A*B/(C-D)==A*B/(C-D))return 1; if(A*B/C*D==24&&1.0*A*B/C*D==A*B/C*D)return 1; if(A*B/C/D==24&&1.0*A*B/C/D==A*B/C/D)return 1; if(A/B+C+D==24&&1.0*A/B==A/B)return 1; if(A/(B+C)+D==24&&1.0*A/(B+C)==A/(B+C))return 1; if(A/(B+C+D)==24&&1.0*A/(B+C+D)==A/(B+C+D))return 1; if(A/B+C-D==24&&1.0*A/B==A/B)return 1; if(A/(B+C)-D==24&&1.0*A/(B+C)==A/(B+C))return 1; if(B+C-D!=0&&A/(B+C-D)==24&&1.0*A/(B+C-D)==A/(B+C-D))return 1; if(A/B+C*D==24&&1.0*A/B==A/B)return 1; if(A/(B+C)*D==24&&1.0*A/(B+C)*D==A/(B+C)*D)return 1; if(A/(B+C*D)==24&&1.0*A/(B+C*D)==A/(B+C*D))return 1; if(A/B+C/D==24&&1.0*A/B==A/B&&1.0*C/D==C/D)return 1; if(A/(B+C)/D==24&&1.0*A/(B+C)/D==A/(B+C)/D)return 1; if(A/(B+C/D)==24&&1.0*C/D==C/D&&1.0*A/(B+C/D)==A/(B+C/D))return 1; if((A/B+C)/D==24&&1.0*A/B==A/B&&1.0*(A/B+C)/D==(A/B+C)/D)return 1; if(A/B-C+D==24&&1.0*A/B==A/B)return 1; if(B-C!=0&&A/(B-C)+D==24&&1.0*A/(B-C)==A/(B-C))return 1; if(B-C+D!=0&&A/(B-C+D)==24&&1.0*A/(B-C+D)==A/(B-C+D))return 1; if(A/B-C-D==24&&1.0*A/B==A/B)return 1; if(B-C!=0&&A/(B-C)-D==24&&1.0*A/(B-C)==A/(B-C))return 1; if(B-C-D!=0&&A/(B-C-D)==24&&1.0*A/(B-C-D)==A/(B-C-D))return 1; if(A/B-C*D==24&&1.0*A/B==A/B)return 1; if(B-C!=0&&A/(B-C)*D==24&&1.0*A/(B-C)*D==A/(B-C)*D)return 1; if(B-C*D!=0&&A/(B-C*D)==24&&1.0*A/(B-C*D)==A/(B-C*D))return 1; if(A/B-C/D==24&&1.0*A/B==A/B&&1.0*C/D==C/D)return 1; if(B-C!=0&&A/(B-C)/D==24&&1.0*A/(B-C)/D==A/(B-C)/D)return 1; if(B-C/D!=0&&A/(B-C/D)==24&&1.0*C/D==C/D&&1.0*A/(B-C/D)==A/(B-C/D))return 1; if((A/B-C)/D==24&&1.0*A/B==A/B&&1.0*(A/B-C)/D==(A/B-C)/D)return 1; if(A/B*C+D==24&&1.0*A/B*C==A/B*C)return 1; if(A/(B+C)*D==24&&1.0*A/(B+C)*D==A/(B+C)*D)return 1; if(A/(B+C*D)==24&&1.0*A/(B+C*D)==A/(B+C*D))return 1; if(A/B*C-D==24&&1.0*A/B*C==A/B*C)return 1; if(A/B*(C-D)==24&&1.0*A/B*(C-D)==A/B*(C-D))return 1; if(B*C-D!=0&&A/(B*C-D)==24&&1.0*A/(B*C-D)==A/(B*C-D))return 1; if(A/B*C*D==24&&1.0*A/B*C*D==A/B*C*D)return 1; if(A/B*C/D==24&&1.0*A/B*C/D==A/B*C/D)return 1; if(A/B/C+D==24&&1.0*A/B/C==A/B/C)return 1; if(A/B/(C+D)==24&&1.0*A/B/(C+D)==A/B/(C+D))return 1; if(A/B/C-D==24&&1.0*A/B/C==A/B/C)return 1; if(C-D!=0&&A/B/(C-D)==24&&1.0*A/B/(C-D)==A/B/(C-D))return 1; if(A/B/C*D==24&&1.0*A/B/C*D==A/B/C*D)return 1; if(A/B/C/D==24&&1.0*A/B/C/D==A/B/C/D)return 1; return 0; } int main() { #ifdef DEBUG freopen("input.in", "r", stdin); //freopen("output.out", "w", stdout); #endif //ios::sync_with_stdio(false); //cin.tie(0); //cout.tie(0); //scanf("%d",&t); //while(t--){ scanf("%d%d%d%d",&a[1],&a[2],&a[3],&a[4]); ans=0; while(cnt<24){ ++cnt; next_permutation(a+1,a+5); if(check()){ans=1;break;} } cout<<(ans?"Yes":"No")<<endl; //} #ifdef DEBUG printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif //cout << "Hello world!" << endl; return 0; }

Problem B Pikachu

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=1

补题地址：http://47.96.116.66/problem.php?id=2111

题意：

第一种操作对[l,r]区间内每幢房子塞入一个皮卡丘; 第二种操作对第l次到第r次的操作重复一遍。

问依次进行m次操作后每幢房子内皮卡丘的个数。

题解：

可以 O(n)维护两个差分数组，一个是针对重复操作的差分数组，一个是针对当前房子塞入皮卡丘的个数的差分数组。对第二个差分数组的每次修改的大小是当前操作重复操作次数。因为每一次第二种操作总是针对之前的操作，所以要倒着跑一遍。最后对针对当前房子塞入皮卡丘的个数的差分数组求个前缀和就好了。

C++版本一

Problem C Raichu

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=2

补题地址：http://47.96.116.66/problem.php?id=2112

题意：

第一种操作对第x幢房子塞入一个吕子乔; 第二种操作对第x次操作重复一遍。问依次进行m次操作后每幢房子内吕子乔的个数（初始每幢房子都是空的）。

题解：根据题意可以得出结论一个第二种操作回溯到头一定是第一种操作,一定是一个链状的结构。同时我们很容易维护每个第二种操作的头节点是谁,可以通过直接继承前一次操作的头节点

C++版本一

Problem D 本题不用算法

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=3

补题地址：http://47.96.116.66/problem.php?id=2113

题意：给你三个数Ａ，Ｂ，Ｃ，你需要找到另外三个数ａ，ｂ，ｃ分别是对应Ａ，Ｂ，Ｃ的因数，请你输出一共有多少种方案数（三个数顺序改变视为同一种方案）

题解：容斥+组合数学+状态压缩

无非只有7种状况

001：只是A的约数，不是BC的约数，这是可以容斥的。下同。

010：只是B的因数。

100：只是C的因数。

011：只是AB的因数。

101：只是AC的因数。

110：只是BC的因数。

111：同时是ABC的因数

我们现在就可以枚举每条边的状态了，三重循环7*7*7次。那么接下来我们考虑什么样的边是满足条件的边呢：

给小长方体一个合适的翻转，使三条边至少分别是ABC点的因子。怎么做呢？上面我们按位处理了每条边的状态，所以只要没枚举一下变得顺序（翻转正方形）使得和ABC一一对应（对应位为1）

bool check(int a,int b,int c){ if((a&1) && (b&2) && (c&4)) return true; if((a&1) && (c&2) && (b&4)) return true; if((b&1) && (a&2) && (c&4)) return true; if((b&1) && (c&2) && (a&4)) return true; if((c&1) && (a&2) && (b&4)) return true; if((c&1) && (b&2) && (a&4)) return true; return false; }

好了接下来我们找到合适的三边了，那么怎么计算此时的种类呢？这也是本体的一大亮点。

1.如果a，b，c是不同的状态得来的，那么ok没有重复。每种数量选一个，也就是乘起来就好啦~

2.但是如果有两个数或者三个数是相同的状态，这就要求我们从一定数量中选择有重复个元素。举个例子，如果ab状态相同，都是cond[s]，那么我们应该从cond[s]中选两个，并且可以重复即a选了k，b也选了k 这就需用到有重复的组合公式：如果从n个元素中选择r个有重复元素，其公式为：

另外，我们用use数组将计算过程一般化，use[i]即为r。请好好体会。这里非常巧妙。

参考文章：原题原博客

C++版本一

#include<iostream> #include<cstdio> #include<cstring> typedef long long ll; using namespace std; const int maxn = 1e5 + 10; int fac[maxn]; void fac_table(int n){ for(int i = 1;i < n;i++) for(int j = i;j < n;j+=i) fac[j]++; return; } ll C(int n,int m){ ll ans = 1; for(int i = 1;i <= m;i++){ ans = ans*(n-i+1)/i; } return ans; } int gcd(int a,int b){ if(b == 0) return a; return gcd(b,a%b); } bool check(int a,int b,int c){ if((a&1) && (b&2) && (c&4)) return true; if((a&1) && (c&2) && (b&4)) return true; if((b&1) && (a&2) && (c&4)) return true; if((b&1) && (c&2) && (a&4)) return true; if((c&1) && (a&2) && (b&4)) return true; if((c&1) && (b&2) && (a&4)) return true; return false; } int condi[10],use[10]; int main(){ fac_table(maxn); ll T; int x,y,z;ll ans; scanf("%lld",&T); while(T--){ scanf("%d%d%d",&x,&y,&z); int xy = gcd(x,y); int xz = gcd(x,z); int yz = gcd(y,z); int xyz = gcd(xy,z); condi[1] = fac[x] - fac[xy] - fac[xz] + fac[xyz];//001 condi[2] = fac[y] - fac[xy] - fac[yz] + fac[xyz];//010 condi[4] = fac[z] - fac[xz] - fac[yz] + fac[xyz];//100 condi[3] = fac[xy] - fac[xyz];//011 condi[5] = fac[xz] - fac[xyz];//101 condi[6] = fac[yz] - fac[xyz];//110 condi[7] = fac[xyz]; ans = 0; for(int a = 1;a < 8;a++) for(int b = a;b < 8;b++) for(int c = b;c < 8;c++) if(check(a,b,c) == true){ memset(use,0,sizeof(use)); use[a]++;use[b]++;use[c]++; ll tmp = 1; for(int i = 1;i < 8;i++) if(use[i] != 0) tmp = tmp*C(condi[i] + use[i]-1,use[i]); if(tmp > 0) ans += tmp; } printf("%lld\n",ans); } return 0; }

Problem E 博弈

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=4

补题地址：http://47.96.116.66/problem.php?id=2114

题意：小A和小B进行一场博弈，有一个串有n颗珠子的圆环，每次一个人可以取走连续的1颗或2颗，问谁会赢。

题解：如果是1或2，那么小A取走直接赢，否则小B赢，因为他可以变成对称博弈。

C++版本一

Problem F 地下迷宫

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=5

补题地址：http://47.96.116.66/problem.php?id=2115

题意：任意两点之间最短路

题解：先建成一颗生成树，然后对于剩下的边的所有点跑一边最短路，记录下这些点到其他所有点的距离，然后跑树上最短路，再暴力枚举剩下的边，取距离最小值。

C++版本一

Problem G 简简单单的数学题

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=6

补题地址：http://47.96.116.66/problem.php?id=2116

题意：⌊a⌋ +⌈b⌉+c(四舍五入)+d^n

题解：快速幂+乘法优化

C++版本一

题解：快速幂+__int128

C++版本二

快速幂+乘法优化，变成1e6进制的数

Problem H 拼可可

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=7

补题地址：http://47.96.116.66/problem.php?id=2117

题意：至少多少个a*b的矩形才能拼成一个正方形？

题解：求a，b的lcm即可

C++版本一

Problem I 签到题

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=8

补题地址：http://47.96.116.66/problem.php?id=2118

题意：

题解：二分答案，差分检查。

C++版本一

Problem J 无尽递增

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=9

补题地址：http://47.96.116.66/problem.php?id=2119

题意：找一个最长的子序列，1111122222.

题解：DP

转化题意后，其实就是找出最长的1111222211112222，我们可以开dp【4】，分别表示以红色标出的值为结尾的最长子序列。

转移公式为：

C++版本一

Problem K 消消乐

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=10

补题地址：http://47.96.116.66/problem.php?id=2120

题意：

题解：区间dp + 记忆化搜索

dp[i][j][k] : （区间 [i, j] 后面带上一段和 j 颜色相同的且长度为 k ）的消消乐最大积分

1.消最后一段颜色和 j 颜色相同的

dp[i][j][k] <-- dp[i][j-1][0] + (k+1)^3

2.对于i <= l < j，如果 l 和 j 的颜色相同，那么可以把 [l+1, j-1]消掉, 那么剩下的一段就有 k+1 个和 l 相同的一段了

dp[i][j][k] <-- dp[i][l][k+1] + dp[l+1][j-1][0]

答案就是dp[1][n][0]，采用记忆化搜索更方便转移

C++版本一

Problem L 寻宝

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=11

补题地址：http://47.96.116.66/problem.php?id=2121

题意：

题解：

Exkmp预处理出数组，后缀数组也行，查询由于强制在线主席树顺便搞搞就好，对于会这两个算法的人这题应该是一道一眼题，而且由于懒得造数据，所以数据都是循环的，说不定有什么优秀的暴力也能过

C++版本一

Problem M 智慧爷的蛋糕

比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=12

补题地址：http://47.96.116.66/problem.php?id=2122

题意：求后缀子串的最长公共前缀子串

题解：SA+LCP+ST

(方法一) 后缀数组 ST表预处理复杂度 nlogn

(方法二) 字符串哈希+二分 qlog(n)+n

C++版本一

题解：后缀数组 ST表预处理

最新回复(0)