网站开发 图片存放,2017优惠券网站怎么做,dw 做静态网站,网站图片多大比赛链接
好忙好忙好忙#xff0c;慢慢补老比赛的题解了。
这场没啥算法#xff0c;全是思维。有也是BFS#xff0c;屎。 A. Special Characters
题意#xff1a;
您将得到一个整数 n n n 。
您的任务是构建一串大写的拉丁字母。此字符串中必须正好有 n n n 个特殊字…比赛链接
好忙好忙好忙慢慢补老比赛的题解了。
这场没啥算法全是思维。有也是BFS屎。 A. Special Characters
题意
您将得到一个整数 n n n 。
您的任务是构建一串大写的拉丁字母。此字符串中必须正好有 n n n 个特殊字符。让我们称一个字符为特殊字符如果它恰好等于它的一个邻居。
例如AAABAACC字符串中有 6 6 6 个特殊字符位置为 1 1 1 、 3 3 3 、 5 5 5 、 6 6 6 7 7 7 和 8 8 8 。
打印任何合适的字符串或报告没有这样的字符串。
思路
发现如果是 AABBAABB 这样子的序列的话每个字符都会是特殊字符。但是这样的只能构造出 n n n 为偶数时候的情况。考虑能否构造出 n n n 为奇数时候的情况。
因为一个字符为特殊字符只和它的左右相邻的字符有关再往前是什么它是不在意的。所以我们构造 n n n 为奇数时候的情况时前面的部分仍然用类似 AABB 这种形式来构造因为三个及以上连续的字符挨在一起时中间的字符就不是特殊字符不会产生贡献了只有两头的字符会产生贡献它就和两个字符的等价所以我们不妨规定挨在一起的相同字符最多有两个。
于是如果前面的部分结尾为 A A AA AA 时我们后面会补上 B B B这时这个 B B B 不是特殊字符因此这时凑不出奇数情况。然后我们继续向后补字符如果我们补 A A A这个 A A A 也不是特殊字符凑不出奇数情况如果补 B B B这时补的两个 B B B 都同时成为了特殊字符相当于上面说的 A A B B AABB AABB 形式仍然凑不出奇数情况。
如果我们在补上 B A BA BA然后继续向后补字符就会重复上面的讨论。因此无论怎么补我们都凑不出奇数情况。这就意味着 n n n 为奇数时是无解的。
code
#include iostream
#include cstdio
#include cstring
using namespace std;
const int maxn55;int T,n;
char s[maxn];int main(){cinT;while(T--){cinn;if(n1){coutNOendl;continue;}else coutYESendl;for(int i1;in;i4)s[i]s[i1]A;for(int i3;in;i4)s[i]s[i1]B;for(int i1;in;i)couts[i];coutendl;}return 0;
}B. Array Fix
题意
您将得到一个长度为 n n n 的整数数组 a a a 。
您可以执行以下操作任意次数可能为零取数组 a a a 中至少为 10 10 10 的任何元素将其删除然后在相同位置插入该元素所包含的数字按它们出现在该元素中的顺序。例如 如果我们将此操作应用于数组 [ 12 , 3 , 45 , 67 ] [12, 3, 45, 67] [12,3,45,67] 的第 3 3 3 个元素则数组将变为 [ 12 , 3 , 4 , 5 , 67 ] [12, 3, 4, 5, 67] [12,3,4,5,67] 。 如果我们将此操作应用于数组 [ 2 , 10 ] [2, 10] [2,10] 的第 2 2 2 个元素则数组将变为 [ 2 , 1 , 0 ] [2, 1, 0] [2,1,0] 。
您的任务是确定是否可以使用上述操作任意次数使 a a a 按非降序排序。换句话说您必须确定是否可以将数组 a a a 转换为 a 1 ≤ a 2 ≤ ⋯ ≤ a k a_1 \le a_2 \le \dots \le a_k a1≤a2≤⋯≤ak 其中 k k k 是数组 a a a 的当前长度。
思路
先注意一下题目说了 0 ≤ a i ≤ 99 0 \le a_i \le 99 0≤ai≤99因此 a i a_i ai 最多就是个两位数。
因为是非降序的所以从某一位开始也许后面就都变成了两位及以上的数这时这些数不能被拆数位否则变成一位数之后就会变小。反之在此之前所有的数都得是一位数否则某个两位数后面出现了一位数就不满足非降序的条件了。因此我们找到这个分界点把分界点之前的所有数都拆掉然后看满不满足条件就行了。
根据上面的分析这个分界点之后的数都是不拆数位就满足非降序的所以我们从后向前找到第一个不满足条件的位置这个位置就是分界点了。从这个位置向前拆数。一个数拆开后个位放在后面十位放在前面。所以我们没必要真的把两个新的数插入到当前位置这样比较麻烦。
判断这个数是否和后一个数满足非降序的关系我们直接看一下当前数的十位不小于个位并且个位不小于后一个数之后用十位代替这个数再向前找即可。
code
#include iostream
#include cstdio
using namespace std;
const int maxn55;int T,n,a[maxn];int main(){cinT;while(T--){cinn;for(int i1;in;i)cina[i];int idx;for(idxn-1;idx1;idx--)if(a[idx]a[idx1])break;// cout***idxendl;bool flagtrue;for(int iidx;i1;i--){if(a[i]/10a[i]%10 || a[i]%10a[i1]){flagfalse;break;}if(a[i]10)a[i]/10;}puts((flag)?YES:NO);}return 0;
}C. Arrow Path
题意
有一个网格由 2 2 2 行和 n n n 列组成。这些行从上到下从 1 1 1 到 2 2 2 进行编号。列从左到右从 1 1 1 到 n n n 进行编号。网格的每个单元格都包含一个指向左侧或右侧的箭头。没有箭头指向网格外。
有一个机器人在单元格 ( 1 , 1 ) (1, 1) (1,1) 中启动 。每一秒钟都有以下两个动作相继发生 首先机器人向左、向右、向下或向上移动它不能尝试走出网格也不能跳过这次移动 然后它沿着放置在当前单元格移动后结束的单元格中的箭头移动。
您的任务是确定机器人是否可以到达单元 ( 2 , n ) (2, n) (2,n) 。
思路
比较明显的BFS。
code
#include iostream
#include cstdio
#include cstring
#include queue
#include vector
#define pii pairint,int
using namespace std;
const int maxn2e55;int T,n;
string mp[5];int fx[]{1,-1,0,0},fy[]{0,0,1,-1};int main(){cinT;while(T--){cinn;cinmp[1]mp[2];mp[1] mp[1];mp[2] mp[2];queuepii q;vectorvectorbool vis(5,vectorbool(n5,false));q.push(pii(1,1));vis[1][1]true;bool flagfalse;while(!q.empty()){int uxq.front().first,uyq.front().second;q.pop();if(ux2 uyn){flagtrue;break;}for(int i0,x,y;i4;i){xuxfx[i],yuyfy[i];if(x1 || x2 || y1 || yn)continue;if(mp[x][y])y--;else y;if(!vis[x][y]){q.push(pii(x,y));vis[x][y]true;}}}puts((flag)?YES:NO);}return 0;
}D. Tandem Repeats?
题意
您将得到一个字符串 s s s 它由小写的拉丁字母以及问号组成。
串联重复序列tandem repeat是指长度为偶数的串满足其前一半等于其后一半。
您的目标是将每个问号替换为某个小写拉丁字母求出最大可能的串联重复序列子串的长度。
思路
考虑到这个串联重复序列比如 a b c a b c abcabc abcabc说白了就是第 1 1 1 个字符向后 3 3 3 个长度的子串与第 4 4 4 个字符向后 3 3 3 个长度的子串相同。那么一定第 2 2 2 个字符向后 2 2 2 个长度的子串与第 5 5 5 个字符向后 2 2 2 个长度的子串相同前者可以由后者推出来。
所以我们设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示从第 i i i 个字符开始的子串和第 j j j 个字符开始的子串最长匹配长度是多少。当第 i i i 个字符和第 j j j 个字符相同时两个字符真的相同或者其中一个为 ? ? ?可以万能匹配 d p [ i ] [ j ] dp[i][j] dp[i][j] 就可以从 d p [ i 1 ] [ j 1 ] 1 dp[i1][j1]1 dp[i1][j1]1 推过来。因为是从 i 1 , j 1 i1,j1 i1,j1 推来的因此 i , j i,j i,j 的枚举需要反着从 n n n 到 1 1 1。
不过 i ∼ i d p [ i ] [ j ] − 1 i\sim idp[i][j]-1 i∼idp[i][j]−1 与 j ∼ j d p [ i ] [ j ] − 1 j\sim jdp[i][j]-1 j∼jdp[i][j]−1 两个区间的子串匹配不一定就是串联重复序列它需要正好是 i d p [ i ] [ j ] − 1 j − 1 idp[i][j]-1j-1 idp[i][j]−1j−1 即 j − i d p [ i ] [ j ] j-idp[i][j] j−idp[i][j]也就是前后两个子串正好相接。 d p [ i ] [ j ] dp[i][j] dp[i][j] 如果大于 j − i j-i j−i这时可以直接截取长为 j − i j-i j−i 的一段作为串联重复序列反之就一定无法成为串联重复序列。
code
#include cstdio
#include iostream
#include cstring
#include vector
using namespace std;int T,n;
string s;int main(){cinT;while(T--){cins;ns.length();s s;vectorvectorint dp(n5,vectorint(n5,0));for(int in;i1;i--){for(int ji-1;j1;j--){if(s[i]? || s[j]? || s[i]s[j])dp[i][j]dp[i1][j1]1;}}int ans0;for(int i1;in;i){for(int j1;ji;j){int tdp[i][j];if(ti-j)ti-j;else continue;ansmax(ans,t);}}coutans*2endl;}return 0;
}E. Clique Partition
题意
给出两个整数 n n n 和 k k k 。在 n n n 个顶点上有一个图编号从 1 1 1 到 n n n 它最初没有边。你必须给每个顶点分配一个整数设 a i a_i ai 是顶点 i i i 上的整数。所有 a i a_i ai 都应该是从 1 1 1 到 n n n 的不同整数。
指定整数后对于每对顶点 ( i , j ) (i, j) (i,j) 如果 ∣ i − j ∣ ∣ a i − a j ∣ ≤ k |i - j| |a_i - a_j| \le k ∣i−j∣∣ai−aj∣≤k 则在它们之间添加一条边。
您的目标是创建一个图该图可以划分为最小可能对于给定的 n n n 和 k k k 值数量的团Clique。
图的每个顶点应该恰好属于一个团。
团是一组顶点其中的每一对顶点都与一条边相连。由于布莱德斯特没有真正提高他的编程技能他无法解决问题 “给一个图将其划分为最小数量的团”。因此我们要求您打印分区本身。
思路
构造题构造方法不好想。如果想出了构造方法写是比较容易的。
要团的个数最少那么就考虑让团包含的点最多。因为 a i a_i ai 互不重复所以 ∣ a i − a j ∣ |a_i - a_j| ∣ai−aj∣ 至少会是 1 1 1那么 ∣ i − j ∣ |i - j| ∣i−j∣ 最大就是 k − 1 k-1 k−1这时 j − i 1 j-i1 j−i1 最大就是 k k k。也就是说团最多可能包含 k k k 个点。
考虑如果一个团能否塞入 k k k 个点不妨使用顶点 1 ∼ k 1\sim k 1∼k。而且为了不影响到其他团所以我们尽量给它们分配 1 ∼ k 1\sim k 1∼k 的编号。
首先第 1 1 1 个数和第 k k k 个数必须差 1 1 1否则这一对一定不满足条件。同理第 1 1 1 个数和第 k − 1 k-1 k−1 个数必须差 ≤ 2 \le 2 ≤2第 2 2 2 个数和第 k k k 个数必须差 ≤ 2 \le 2 ≤2。考虑把第一个数置为中间数 k / 2 k/2 k/2这样中间数两边都有空间我们把中间数前面的数降序放在前半部分中间数后面的数降序放在后半部分。即 k / 2 , k / 2 − 1 , … , 1 , k , k − 1 … , k / 2 2 , k / 2 1 k/2,k/2-1,\dots,1,k,k-1\dots,k/22,k/21 k/2,k/2−1,…,1,k,k−1…,k/22,k/21
还是比较好验证这么构造的正确性的前半部分一定满足条件后半部分一定满足条件。前半部分取一个数后半部分取一个数的情况也满足条件。综合一下所有情况都满足条件。
这样 1 ∼ k 1\sim k 1∼k 的情况就构造出来了因为相对位置和相对大小是不变的所以后面的每个团也是这样构造就可以了。
有时候会剩下一些点不足 k k k 个。构造方式同理把上面的序列截掉后面部分即可大概就是这样
如果 n ≤ k / 2 n\le k/2 n≤k/2则 n , n − 1 , … , 1 n,n-1,\dots,1 n,n−1,…,1如果 k / 2 n k k/2\lt n\lt k k/2nk则 k / 2 , k / 2 − 1 , … , 1 , n , n − 1 … , k / 2 2 , k / 2 1 k/2,k/2-1,\dots,1,n,n-1\dots,k/22,k/21 k/2,k/2−1,…,1,n,n−1…,k/22,k/21
团的个数也就很显然了是 ⌈ n k ⌉ \left\lceil\dfrac nk\right\rceil ⌈kn⌉。第 i i i 个点所属的团显然就是第 ⌈ i k ⌉ \left\lceil\dfrac ik\right\rceil ⌈ki⌉ 个团。
code
#include iostream
#include cstdio
#include algorithm
using namespace std;
const int maxn45;int T,n,k;
int a[maxn];int main(){cinT;while(T--){cinnk;for(int i1,lenk;in;ik){if(ik-1n){for(int ji;jilen;j)a[j]j;reverse(ai,ailen/2);reverse(ailen/2,ailen);}else {if(ilen/2n){for(int ji;jn;j)a[j]j;reverse(ai,an1);}else {for(int ji;jn;j)a[j]j;reverse(ai,ailen/2);reverse(ailen/2,an1);}}}
// cout***;for(int i1;in;i)printf(%d ,a[i]);puts();cout(nk-1)/kendl;for(int i1;in;i){printf(%d ,(ik-1)/k);}puts();}return 0;
}
文章转载自： http://www.morning.ktmbp.cn.gov.cn.ktmbp.cn http://www.morning.ptmgq.cn.gov.cn.ptmgq.cn http://www.morning.nfbkz.cn.gov.cn.nfbkz.cn http://www.morning.jcnmy.cn.gov.cn.jcnmy.cn http://www.morning.xhgxd.cn.gov.cn.xhgxd.cn http://www.morning.hptbp.cn.gov.cn.hptbp.cn http://www.morning.wchcx.cn.gov.cn.wchcx.cn http://www.morning.zkgpg.cn.gov.cn.zkgpg.cn http://www.morning.cytr.cn.gov.cn.cytr.cn http://www.morning.mxgpp.cn.gov.cn.mxgpp.cn http://www.morning.mdgpp.cn.gov.cn.mdgpp.cn http://www.morning.mcwrg.cn.gov.cn.mcwrg.cn http://www.morning.xrct.cn.gov.cn.xrct.cn http://www.morning.ykyfq.cn.gov.cn.ykyfq.cn http://www.morning.dwrjj.cn.gov.cn.dwrjj.cn http://www.morning.nzcgj.cn.gov.cn.nzcgj.cn http://www.morning.ptqbt.cn.gov.cn.ptqbt.cn http://www.morning.hpxxq.cn.gov.cn.hpxxq.cn http://www.morning.qnftc.cn.gov.cn.qnftc.cn http://www.morning.pangucheng.cn.gov.cn.pangucheng.cn http://www.morning.qwmdx.cn.gov.cn.qwmdx.cn http://www.morning.sfqtf.cn.gov.cn.sfqtf.cn http://www.morning.sftpg.cn.gov.cn.sftpg.cn http://www.morning.lsxabc.com.gov.cn.lsxabc.com http://www.morning.kcsx.cn.gov.cn.kcsx.cn http://www.morning.ynwdk.cn.gov.cn.ynwdk.cn http://www.morning.hjssh.cn.gov.cn.hjssh.cn http://www.morning.xq3nk42mvv.cn.gov.cn.xq3nk42mvv.cn http://www.morning.qgxnw.cn.gov.cn.qgxnw.cn http://www.morning.ktsth.cn.gov.cn.ktsth.cn http://www.morning.zdbfl.cn.gov.cn.zdbfl.cn http://www.morning.myxps.cn.gov.cn.myxps.cn http://www.morning.nmnhs.cn.gov.cn.nmnhs.cn http://www.morning.zgdnd.cn.gov.cn.zgdnd.cn http://www.morning.rnkq.cn.gov.cn.rnkq.cn http://www.morning.trnhy.cn.gov.cn.trnhy.cn http://www.morning.mrccd.cn.gov.cn.mrccd.cn http://www.morning.aiai201.cn.gov.cn.aiai201.cn http://www.morning.ckctj.cn.gov.cn.ckctj.cn http://www.morning.bwjgb.cn.gov.cn.bwjgb.cn http://www.morning.phcqk.cn.gov.cn.phcqk.cn http://www.morning.wckrl.cn.gov.cn.wckrl.cn http://www.morning.yhljc.cn.gov.cn.yhljc.cn http://www.morning.rqfzp.cn.gov.cn.rqfzp.cn http://www.morning.kzqpn.cn.gov.cn.kzqpn.cn http://www.morning.sqtsl.cn.gov.cn.sqtsl.cn http://www.morning.chtnr.cn.gov.cn.chtnr.cn http://www.morning.wmpw.cn.gov.cn.wmpw.cn http://www.morning.rgrz.cn.gov.cn.rgrz.cn http://www.morning.clfct.cn.gov.cn.clfct.cn http://www.morning.kqrql.cn.gov.cn.kqrql.cn http://www.morning.smdiaosu.com.gov.cn.smdiaosu.com http://www.morning.kydrb.cn.gov.cn.kydrb.cn http://www.morning.wmdlp.cn.gov.cn.wmdlp.cn http://www.morning.mzwfw.cn.gov.cn.mzwfw.cn http://www.morning.btlsb.cn.gov.cn.btlsb.cn http://www.morning.ryqsq.cn.gov.cn.ryqsq.cn http://www.morning.rdlong.com.gov.cn.rdlong.com http://www.morning.rzrbw.cn.gov.cn.rzrbw.cn http://www.morning.fmrwl.cn.gov.cn.fmrwl.cn http://www.morning.xmnlc.cn.gov.cn.xmnlc.cn http://www.morning.skbbt.cn.gov.cn.skbbt.cn http://www.morning.rkrl.cn.gov.cn.rkrl.cn http://www.morning.lffrh.cn.gov.cn.lffrh.cn http://www.morning.qclmz.cn.gov.cn.qclmz.cn http://www.morning.mqmmc.cn.gov.cn.mqmmc.cn http://www.morning.fkyqm.cn.gov.cn.fkyqm.cn http://www.morning.grcfn.cn.gov.cn.grcfn.cn http://www.morning.ygbq.cn.gov.cn.ygbq.cn http://www.morning.rdqzl.cn.gov.cn.rdqzl.cn http://www.morning.rxnl.cn.gov.cn.rxnl.cn http://www.morning.rgxn.cn.gov.cn.rgxn.cn http://www.morning.nbnpb.cn.gov.cn.nbnpb.cn http://www.morning.mjdbd.cn.gov.cn.mjdbd.cn http://www.morning.demoux.com.gov.cn.demoux.com http://www.morning.gnkdp.cn.gov.cn.gnkdp.cn http://www.morning.sgrwd.cn.gov.cn.sgrwd.cn http://www.morning.bkgfp.cn.gov.cn.bkgfp.cn http://www.morning.fgxws.cn.gov.cn.fgxws.cn http://www.morning.pzrrq.cn.gov.cn.pzrrq.cn
