遵义本地网站,网页无法访问qq可以登陆,wordpress 会员,微信朋友圈广告投放DAY 1 B 组 T1 游戏 Description Alice和Bob在玩一个游戏#xff0c;游戏是在一个N*N的矩阵上进行的#xff0c;每个格子上都有一个正整数。 当轮到Alice/Bob时#xff0c;他/她可以选择最后一列或最后一行#xff0c;并将其删除#xff0c; 但必须保证选择的这一行或这一… DAY 1 B 组 T1 游戏 Description Alice和Bob在玩一个游戏游戏是在一个N*N的矩阵上进行的每个格子上都有一个正整数。 当轮到Alice/Bob时他/她可以选择最后一列或最后一行并将其删除 但必须保证选择的这一行或这一列所有数的和为偶数。如果他/她不能删除最后一行或最后一列那么他/她就输了。 两人都用最优策略来玩游戏Alice先手问Alice是否可以必胜 Input 第一行T表示数据组数对于每组数据的第一行N接下来N行每行N个数描述这个矩阵 Output 如果Alice必胜输出W否则输出L Sample Input 2 2 2 4 6 8 3 5 4 2 1 5 9 7 3 8 Sample Output L W Data Constraint Hint 100%数据满足1N1000 保证每一行或每一列的和不会超过2*10^91T530%数据满足1N550%数据满足1N10070%数据满足1N500 正解 记忆化搜索把必胜状态设为1必输状态设为0能到1的就是1否则就是0 从一个小区域一点一点往外扩从而进行搜索。最后记得特判一下能否去取这一行OR列 #includeiostream
#includecstdio
#includecstring
using namespace std;
int dp[1050][1050],n,t;
int x[1050][1050],map[1050][1050];
int main(){//freopen(game10.in,r,stdin);//freopen(1.out,w,stdout);scanf(%d,t);while(t--){memset(dp,0,sizeof(dp));memset(x,0,sizeof(x));memset(map,0,sizeof(map));scanf(%d,n);for(register int i1;in;i)for(register int j1;jn;j)scanf(%d,map[i][j]);for(register int i1;in;i)for(register int j1;jn;j)x[i][j]map[i][j]x[i-1][j]x[i][j-1]-x[i-1][j-1];dp[1][1]!(map[1][1]%20);for(register int i1;in;i){for(register int j1;jn;j){if(i1j1) continue;if((i1(x[i][j]-x[i-1][j])%20dp[i-1][j]0)||(j1(x[i][j]-x[i][j-1])%20dp[i][j-1]0))dp[i][j]1;else dp[i][j]0;}}if(dp[n][n]) printf(W\n);else printf(L\n);}return 0;
} View Code T2 六边形 Description 棋盘是由许多个六边形构成的共有5种不同的六边形编号为1到5棋盘的生成规则如下1.从中心的一个六边形开始逆时针向外生成一个个六边形。2.对于刚生成的一个六边形我们要确定它的种类它的种类必须满足与已生成的相邻的六边形不同。3.如果有多个种类可以选我们选择出现次数最少的种类。4.情况3下还有多个种类可以选我们选择数字编号最小的。现在要你求第N个生成的六边形的编号前14个六边形生成图如下 nput 第一行T表示数据组数 接下来T行每行一个数:N,表示第N个六边形 Output 共t行每行一个数表示第N个数据的答案 Sample Input 4 1 4 10 100 Sample Output 1 4 5 5 Data Constraint Hint 100%数据满足1T20 1N1000030%数据满足1N100 正解 first.数数然后可以发现每一层都比里面一层多6个。然后通过这件事情去看第几个空大致在哪里。然后再通过它位置是什么样子的就可以大致知道它里圈位置上是什么然后按题意模拟只要记得有些特殊的地方例如六边形的六个角所影响的空数目以及位置都不同特判一下就可以了 second.由观察不难发现每一个空都要链接六个六边形所以把每一个空的六边形都看作单独的一层把每一圈都扩展即可得到答案 third,可以把六边形摊开成为四边形摊成矩形即可。 code 像我这么懒的人代码还没有写所以我才敢毫无顾忌的放上三种方法啊。
略略略你来打我啊嘻嘻嘻 T3 数列 Description 给你一个长度为N的正整数序列如果一个连续的子序列子序列的和能够被K整除那么就视此子序列合法求原序列包括多少个合法的连续子序列对于一个长度为8的序列,K4的情况2, 1, 2, 1, 1, 2, 1, 2 。它的答案为6子序列是位置1-位置8,2-4,2-7,3-5,4-6,5-7。 Input 第一行T表示数据组数对于每组数据第一行:2个数KN第二行N个数表示这个序列 Output 共T行每行一个数表示答案 Sample Input 2 7 3 1 2 3 4 8 2 1 2 1 1 2 1 2 Sample Output 0 6 Data Constraint Hint 100%数据满足1T201N500001K1000000序列的每个数100000000030%数据满足1T101N,K1000 正解 之前明明做过我还忘了 每次都把和给mod一下开个桶统计一下余数。余数相组合也可以被整除的就是答案的贡献之一。 code #includeiostream
#includecstdio
#includecstring
using namespace std;
#define int long long
int n,val[1001000],t,k,sum,x;
signed main(){//freopen(seq2.in,r,stdin);//freopen(b.out,w,stdout);scanf(%lld,t);while(t--){memset(val,0,sizeof(val));scanf(%lld%lld,k,n);sum0;int ans0;for(register int i1;in;i){scanf(%lld,x);sumx;val[sum%k];sum%k;}for(register int i0;ik;i)ans(val[i]*(val[i]-1))/2;ansval[0];printf(%lld\n,ans);} return 0;
} View Code A 组 T1 水叮当的舞步 Description 水叮当得到了一块五颜六色的格子形地毯作为生日礼物更加特别的是地毯上格子的颜色还能随着踩踏而改变。为了讨好她的偶像虹猫水叮当决定在地毯上跳一支轻盈的舞来卖萌~~~地毯上的格子有N行N列每个格子用一个0~5之间的数字代表它的颜色。水叮当可以随意选择一个0~5之间的颜色然后轻轻地跳动一步地毯左上角的格子所在的联通块里的所有格子就会变成她选择的那种颜色。这里连通定义为两个格子有公共边并且颜色相同。由于水叮当是施展轻功来跳舞的为了不消耗过多的真气她想知道最少要多少步才能把所有格子的颜色变成一样的。 Input 每个测试点包含多组数据。 每组数据的第一行是一个整数N表示地摊上的格子有N行N列。接下来一个N*N的矩阵矩阵中的每个数都在0~5之间描述了每个格子的颜色。N0代表输入的结束。 Output 对于每组数据输出一个整数表示最少步数 Sample Input 2
0 0
0 0
3
0 1 2
1 1 2
2 2 1
0 Sample Output 0
3 Data Constraint 对于30%的数据N5对于50%的数据N6对于70%的数据N7对于100%的数据N8每个测试点不多于20组数据 正解 其实就是一个IDA* 的搜索原题详见洛谷的flood-it 估价函数就是看看每次走完之后还有多少块颜色不同把颜色数目记录一下。 每次最好可以减少一个不同的颜色数所以已走步数加上剩余颜色数若大于已得到的最小步数则可以剪枝 code 既然有原题为何还要在这里找QAQ才不是自己没调出来最后看了别人的代码的缘故呢哼唧 T2 Vani和Cl2捉迷藏 Description vani和cl2在一片树林里捉迷藏……这片树林里有N座房子M条有向道路组成了一张有向无环图。树林里的树非常茂密足以遮挡视线但是沿着道路望去却是视野开阔。如果从房子A沿着路走下去能够到达B那么在A和B里的人是能够相互望见的。现在cl2要在这N座房子里选择K座作为藏身点同时vani也专挑cl2作为藏身点的房子进去寻找 为了避免被vani看见cl2要求这K个藏身点的任意两个之间都没有路径相连。 为了让vani更难找到自己cl2想知道最多能选出多少个藏身点 Input 第一行两个整数NM。接下来M行每行两个整数x、y表示一条从x到y的有向道路。 Output 一个整数K表示最多能选取的藏身点个数。 Sample Input 4 4
1 2
3 2
3 4
4 2 Sample Output 2 Data Constraint 对于20% 的数据N≤10M20。对于60% 的数据, N≤100M1000。对于100% 的数据N≤200M300001x,yN。 正解 n的范围不大而题干中又有“两两之间关系”这种词所以我们容易想到传递闭包 在把他们之间的关系转化之后就是求二分图最小路径覆盖了。 最小路径覆盖n-最大匹配数 感性理解一下吧尽管我不太能说清为什么这么干但是我的直觉告诉我这是对的(づ 3)づ 这有个大佬的博客大家实在不理解就去这里吧。看我ヾ(•ω•)o code 1 #includeiostream2 #includecstdio3 #includealgorithm4 #includecstring5 using namespace std;6 int map[410][410],n,m,match[410],vis[410],x,y;7 inline int read(){8 char cgetchar();int f1,x0;9 while(c9||c0){if(c-)f-1;cgetchar();}
10 while(c0c9){xx*10c-0;cgetchar();}
11 return f*x;
12 }
13 inline bool dfs(int x){
14 for(register int i1;in;i){
15 if(!vis[i]map[x][i]){
16 vis[i]1;
17 if(!match[i]||dfs(match[i])){
18 match[i]x;return true;
19 }
20 }
21 }return false;
22 }
23 inline void floyed(){
24 for(register int i1;in;i)
25 for(register int j1;jn;j)
26 for(register int k1;kn;k)
27 map[i][j]|map[i][k]map[k][j];
28 }
29 int main(){
30 nread();mread();
31 for(register int i1;im;i)
32 map[read()][read()]1;
33 floyed();int ans0;
34 for(register int i1;in;i){
35 memset(vis,false,sizeof(vis));
36 if(dfs(i)) ans;
37 }printf(%d\n,n-ans);
38 } View Code T3 粉刷匠 Description 赫克托是一个魁梧的粉刷匠而且非常喜欢思考 现在神庙里有N根排列成一直线的石柱从1到N标号长老要求用油漆将这些石柱重新粉刷一遍。 赫克托有K桶颜色各不相同的油漆第i桶油漆恰好可以粉刷Ci根石柱并且C1C2C3…CKN即粉刷N根石柱正好用完所有的油漆。 长老为了刁难赫克托要求相邻的石柱颜色不能相同。喜欢思考的赫克托不仅没有立刻开始粉刷反而开始琢磨一些奇怪的问题比如一共有多少种粉刷的方案为了让赫克托尽快开始粉刷请你尽快告诉他答案。 Input 第一行一个正整数T表示测试数据组数对于每一组测试数据数据第1行一个正整数K第2行K个正整数表示第i桶油漆可以粉刷的石柱个数Ci。 Output 对于每组输入数据输出一行一个整数表示粉刷的方案数mod 1000000007 Sample Input 3
3
1 2 3
5
2 2 2 2 2
10
1 1 2 2 3 3 4 4 5 5 Sample Output 10
39480
85937576 Data Constraint 30% N≤10, T≤550% N≤15, T≤580% K≤15,Ci≤5,T≤500100% K≤15,Ci≤6,T≤2000 正解 在ZJOJ上我调出来的正解只有组合数DP但是在其他地方由于放开了空间限制可以用7维记忆化搜索来切题的 这里都会讲一下完整代码只放前者后者会有代码片段听大佬们说后者可以调过但是我真的TCL嘤嘤嘤我真的做不到啊 FIRST.七维记忆化搜索 dp[a][b][c][d][e][f][g]前六维每一维代表着一种油漆数目最后一维就是记录你上一次是用的那种油漆 数组含义就是你第一种油漆用了a桶第二种用了b桶以此类推最后用的是第g种油漆的方案数 1 inline int dfs(int a,int b,int c,int d,int e,int f,int last){2 if(~dp[a][b][c][d][e][f][last]) 3 return dp[a][b][c][d][e][f][last];4 if(a0 b0 c0 d0 e0) 5 return dp[a][b][c][d][e][f][last]1;6 int ans0;7 if(aa-(last2)0) 8 ans(a-(last2))*dfs(a-1,b,c,d,e,f,1);9 if(bb-(last3)0)
10 ans(b-(last3))*dfs(a1,b-1,c,d,e,f,2);
11 if(cc-(last4)0)
12 ans(c-(last4))*dfs(a,b1,c-1,d,e,f,3);
13 if(dd-(last5)0)
14 ans(d-(last5))*dfs(a,b,c1,d-1,e,f,4);
15 if(ee-(last6)0)
16 anse*dfs(a,b,c,d1,e-1,f,5);
17 if(f)
18 anse*dfs(a,b,c,d,e1,f-1,6);
19 return dp[a][b][c][d][e][f][last]ans%mod;
20 } View Code SECOND.组合数DP 至今不会用LETAX的菜鸡落下了伤心的泪水இ௰இ 大家看这位大佬吧我真的不想再打LETAX了我对数学公式有着深深的心理阴影至今为止我还有一篇博客由于数学公式的缘故还在咕咕咕嘤嘤嘤你看我这么可爱我卖个蠢就放过我吧*★,°*:.☆(▽)/$:*.°★* 。(才不是因为自己还有好几天总结没写而犯懒 看这里看这里ヾ(•ω•)o CODE其实楼上链接里有代码了QAQ 1 #includeiostream2 #includecstdio3 #includecstring4 using namespace std;5 #define int long long6 int t,n,ci[20],f[200][100],k;7 int sum[20],c[105][105];8 const int mod1000000007;9 signed main(){
10 c[0][0]1;
11 for(register int i1;i100;i){
12 c[i][0]c[i][i]1;
13 for(register int j1;ji-1;j)
14 c[i][j](c[i-1][j]c[i-1][j-1])%mod;
15 }//组合数预处理
16 scanf(%lld,t);
17 while(t--){
18 scanf(%lld,n);
19 for(register int i1;in;i)
20 scanf(%lld,ci[i]),sum[i]sum[i-1]ci[i];
21 memset(f,0,sizeof(f));f[1][sum[1]-1]1;
22 for(register int i2;in;i)
23 for(register int j0;jsum[i-1];j)
24 if(f[i-1][j])
25 for(register int k1;kci[i];k)
26 for(register int t0;tmin(k,j);t)
27 f[i][jci[i]-t-k]f[i-1][j]*c[j][t]*c[ci[i]-1][k-1]
28 *c[sum[i-1]1-j][k-t],
29 f[i][jci[i]-t-k]%mod;
30 printf(%lld\n,f[n][0]);
31 }
32 } View Code 转载于:https://www.cnblogs.com/fallen-down/p/11321125.html
