秦皇岛 2019 CCPC区域赛部分代码

Decimal Time Limit: 2000/1000 MS (Java/Others) Memory Limit:
131072/131072 K (Java/Others) Total Submission(s): 2010 Accepted
Submission(s): 894

Problem Description 给定一个正整数 n，要求判断 1n
在十进制下是不是一个无限小数。如果是，输出“Yes”，否则输出“No”。

Input 输入第一行一个正整数 T，表示数据组数。

接下来 T 行，每行一个正整数 n(1≤n≤100)。

Hint

样例解释

15=0.2，不是无限小数。

13=0.333⋯，是无限小数。

Output 输出 T 行，每行一个字符串，表示对应测试数据的答案。

Sample Input 2 5 3

Sample Output No Yes

1 最多就当是10 只能被2 和 5 的倍数整除就好

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
int n, m, cas;int main() {ios::sync_with_stdio(false),cin.tie(0);cin >> cas;while(cas --) {cin >> n;while(n % 2 == 0) n /= 2;while(n % 5 == 0) n /= 5;if(n == 1) cout << "No" << endl;else cout << "Yes" << endl;}return 0;
}

Forest Program Time Limit: 4000/2000 MS (Java/Others) Memory Limit:
131072/131072 K (Java/Others) Total Submission(s): 1778 Accepted
Submission(s): 126

Problem Description Z 国近年来一直在考虑遏制国土沙漠化的方案。在 Z
国广阔的疆域上，有着许多的沙漠。沙漠上干旱少雨，荒无人烟，仅有仙人掌能在这种魔鬼环境中生存。经过 Z
国地质探测局的调查，他们得到了沙漠的实地情况。Z 国的地质探测局是一个热爱 CCPC
的机构，他们喜欢使用图论的方式来描述看到的景色。在得到的数据中，沙漠中的每一个连通块都是一棵仙人掌；一个连通块是一棵仙人掌当且仅当连通块中不存在重边和自环，并且每一条边仅被至多一个简单环覆盖。

经过一番评估，Z
国决定通过删去沙漠中的一些边，最终将沙漠变为森林。这里我们定义森林满足：森林中每一个连通块都是一棵树，而树是边数等于点数减一的连通块。现在给定一个包含
n 个点的沙漠，请你求出 Z
国一共有多少种满足要求的沙漠改造方案。两种方案不同当且仅当方案中被删去的边集不同。由于答案可能很大，请将最终答案对 998244353
取模后输出。

Input 多组数据，每组数据第一行输入两个非负整数 n、m，分别表示沙漠中的点数和边数。沙漠中点的编号为 1, 2, …, n。

对于每组数据的第 2 到第 m+1 行，每行输入两个正整数 u、v，表示沙漠中编号为 u 和编号为 v 的两个点之间有边相连。

1≤T≤3，1≤n≤3×105，m≤5×105，1≤u, v≤n 并且 u≠v。

Hint

样例解释

对于第一组样例，只需要至少删去一条边即可变为森林，故一共有 23−1=7 种方案。

Output 对于每一组数据，输出一行一个非负整数，表示答案对 998244353 取模后的值。

Sample Input 2 3 3 1 2 2 3 3 1 6 6 1 2 2 3 3 1 2 4 4 5 5 2

Sample Output 7 49

我们删一个边让他变成树考虑既然仙人掌树必然要删环的边这时它的选边可有的数量是 $p o w （ 2 ， t o t c n t ） - 1$ 个(1是一个也不删) 而树边可以随便删的贡献度是 $p o w (2 ， t o t s u m - t o t c n t)$
然后陈起来就好

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5e5 + 5;
const int maxm = 1e6 + 5;
const int mod = 998244353;
int n, m, cas;int pow_mod(int a, int b) {int res = 1;for(; b; b >>= 1) {if(b & 1)res = res * a % mod;a = a * a % mod;}return res;
}int head[maxn], cnt;
int to[maxn << 1], nxt[maxn << 1];
int f[maxn];
long long tp;
void ade(int a, int b) {to[++ cnt] = b;nxt[cnt] = head[a], head[a] = cnt;
}bool vis[maxn];
int dep[maxn];
int totcnt = 0, totedge = 0;void dfs(int u, int f) {if(vis[u]) return ;vis[u] = 1;dep[u] = dep[f] + 1;for(int i = head[u]; i; i = nxt[i]) {int v = to[i];if(v == f) continue;if(vis[v]) {if(dep[u] + 1 > dep[v]) {totedge ++;totcnt += dep[u] - dep[v] + 1;//   cout << dep[u] - dep[v] + 1 << endl;tp = (tp * (pow_mod(2, dep[u] - dep[v] + 1) - 1)%mod);}} else {totedge ++;dfs(v, u);}}
}signed main() {f[0] = f[1] = 1;for(int i = 2; i <= maxn; i ++) f[i] = (f[i - 1] * i) % mod;cin >> n >> m;for(int i = 1, a, b; i <= m; i ++) {cin >> a >> b;ade(a, b), ade(b, a);}long long ans = 1;for(int i = 1; i <= n; i ++) {if(!vis[i]) {totedge = 0, totcnt = 0;tp = 1;dfs(i, 0);int totsy = totedge - totcnt;ans = ans * pow_mod(2, totsy) % mod * tp % mod;}}cout << ans << endl;return 0;
}

Invoker Time Limit: 15000/12000 MS (Java/Others) Memory Limit:
131072/131072 K (Java/Others) Total Submission(s): 586 Accepted
Submission(s): 100

Problem Description 在 dota2
中有一个叫做祈求者(Invoker)的英雄，在游戏中他有三个基础技能：冰(Quas)，雷(Wex)，火(Exort)，每施展一个技能就可以获得相应属性的一个法球(element)。

但是祈求者同时最多只能有三个法球，即如果他在有三个法球的状态下又使用了某个法球技能，那么他会获得该法球，并失去之前三个法球中最先获得的一个。

不难得出，祈求者身上的三个法球的无顺序组合有 10 种，每一种都对应着一个组合技能：

急速冷却(Cold Snap)，无序组合 QQQ，用 Y 表示
幽灵漫步(Ghost Walk)，无序组合 QQW，用 V 表示
寒冰之墙(Ice Wall)，无序组合 QQE，用 G 表示
电磁脉冲(EMP)，无序组合 WWW，用 C 表示
强袭飓风(Tornado)，无序组合 QWW，用 X 表示
灵动迅捷(Alacrity)，无序组合 WWE，用 Z 表示
阳炎冲击(Sun Strike)，无序组合 EEE，用 T 表示
熔炉精灵(Forge Spirit)，无序组合 QEE，用 F 表示
混沌陨石(Chaos Meteor)，无序组合 WEE，用 D 表示
超震声波(Deafening Blast)，无序组合 QWE，用 B 表示

当祈求者拥有三个法球的时候，使用元素祈唤(Invoke)技能，用 R
表示，便可获得当前法球组合所对应的技能，同时原有的三个法球也不会消失，先后顺序的状态也不会改变。

现在给定一个技能序列，你想按照给定的顺序将他们一个一个地祈唤出来，同时你想用最少的按键来达到目标，所以你想知道对于给定的一个技能序列，最少按多少次键才能把他们都祈唤出来。

注意：游戏开始的时候，祈求者是没有任何法球的。

Input 仅一行一个字符串 s，表示技能序列。其中所有字母都是大写，且在 {B,C,D,F,G,T,V,X,Y,Z} 内。

1≤|s|≤105

Output 仅一行一个正整数，表示最少按键次数。

Sample Input XDTBV

Sample Output 14

Hint

一种按键最少的方案为：QWWREERERWQRQR

就是特蛋疼的DP 情况多的难受 DP还是好像的
109ms timerank 5…

//#include <iostream>
//#include <map>
//#include <algorithm>
//#include <cstring>
//#include <cstdio>
//const int maxn = 1e5 + 100;
//const int INF = 0x3f3f3f3f;
//using namespace std;
//int s[maxn];
//char dic[10][6][4] = {
//	{"QQQ", "QQQ", "QQQ", "QQQ", "QQQ", "QQQ"},
//	{"QQW", "QWQ", "WQQ", "WQQ", "WQQ", "WQQ"},
//	{"QQE", "QEQ", "EQQ", "EQQ", "EQQ", "EQQ"},
//	{"WWW", "WWW", "WWW", "WWW", "WWW", "WWW"},
//	{"QWW", "WQW", "WWQ", "WWQ", "WWQ", "WWQ"},
//	{"WWE", "WEW", "EWW", "EWW", "EWW", "EWW"},
//	{"EEE", "EEE", "EEE", "EEE", "EEE", "EEE"},
//	{"QEE", "EQE", "EEQ", "EEQ", "EEQ", "EEQ"},
//	{"WEE", "EWE", "EEW", "EEW", "EEW", "EEW"},
//	{"QWE", "QEW", "EQW", "EWQ", "WEQ", "WQE"},
//};
//
//int cons(int y1, int i, int y2, int j) {
//	int res = 3;
//	for(int k1 = 0, k2 = 2; k1 < 3; k2 --, k1 ++) {
//		if(dic[y1][i][k2] == dic[y2][j][k1]) res --;
//		else break;
//	}
//	return res;
//}
//
//int dp[6][maxn];       // dp数组
//
//int dif(int a, int pos1, int b, int pos2) {
//	if (dic[a][pos1][0] == dic[b][pos2][0] && dic[a][pos1][1] == dic[b][pos2][1] && dic[a][pos1][2] == dic[b][pos2][2])
//		return 0;
//	if (dic[a][pos1][1] == dic[b][pos2][0] && dic[a][pos1][2] == dic[b][pos2][1])
//		return 1;
//	if (dic[a][pos1][2] == dic[b][pos2][0])
//		return 2;
//	return 3;
//}
//
//int reid(char s) {
//	if(s == 'Y') return 0;
//	if(s == 'V') return 1;
//	if(s == 'G') return 2;
//	if(s == 'C') return 3;
//	if(s == 'X') return 4;
//	if(s == 'Z') return 5;
//	if(s == 'T') return 6;
//	if(s == 'F') return 7;
//	if(s == 'D') return 8;
//	if(s == 'B') return 9;
//}
//char s1[maxn];
//
//int main() {
	init();
//	char tmp;
//	int ans = 0;
//	while(~scanf("%s", s1)) {
//		ans = 0;
//		int len = strlen(s1);
//		for(int i = 0 ; i < len; i ++)
//			s[i] = reid(s1[i]);
//
//		for(int i = 1; i <= len ; i ++) for(int j = 0 ; j < 6 ; j ++)
//				dp[j][i] = INF;
//
//		ans += len;
//		dp[0][0] = dp[1][0] = dp[2][0] = dp[3][0] = dp[4][0] = dp[5][0] = 3;
//		for(int i = 1; i < len ; i ++)
//			for(int j = 0 ; j < 6 ; j ++)
//				for(int k = 0 ; k < 6 ; k ++)
//					dp[j][i] = min(dp[j][i], dp[k][i - 1] + cons(s[i - 1], k, s[i], j));
//		int mi = INF;
//		for(int k = 0 ; k < 6 ; k ++)
//			mi = min(dp[k][len - 1], mi);
//		cout << mi + ans << endl;
//	}
//	return 0;
//}#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int mod = 998244353;
int n, m, cas;int dp[15][maxn];
char s[maxn];struct node {string s1;string s[10];int siz;
} a[15];int reid(char s) {if(s == 'Y') return 1;if(s == 'V') return 2;if(s == 'G') return 3;if(s == 'C') return 4;if(s == 'X') return 5;if(s == 'Z') return 6;if(s == 'T') return 7;if(s == 'F') return 8;if(s == 'D') return 9;if(s == 'B') return 10;if(s == '*') return 11;
}void init() {a[1].s1 = "QQQ";a[2].s1 = "QQW";a[3].s1 = "QQE";a[4].s1 = "WWW";a[5].s1 = "QWW";a[6].s1 = "WWE";a[7].s1 = "EEE";a[8].s1 = "QEE";a[9].s1 = "WEE";a[10].s1 = "QWE";a[11].s[1] = "***";a[11].siz = 1;for(int i = 1; i <= 10; i ++) {sort(a[i].s1.begin(), a[i].s1.end());int t = 0;do {a[i].s[++ t] = a[i].s1;} while(next_permutation(a[i].s1.begin(), a[i].s1.end()));a[i].siz = t;}
}int cons(int y1, int pos1, int y2, int pos2) {if (a[y1].s[pos1][0] == a[y2].s[pos2][0] && a[y1].s[pos1][1] == a[y2].s[pos2][1] && a[y1].s[pos1][2] == a[y2].s[pos2][2])return 0;if (a[y1].s[pos1][1] == a[y2].s[pos2][0] && a[y1].s[pos1][2] == a[y2].s[pos2][1])return 1;if (a[y1].s[pos1][2] == a[y2].s[pos2][0])return 2;return 3;
}void sol(int y1, int y2, int k) {for(int i = 1; i <= a[y2].siz; i ++) {for(int j = 1; j <= a[y1].siz; j ++) {dp[i][k + 1] = min(dp[i][k + 1], dp[j][k] + cons(y1, j, y2, i));}}
}signed main() {init();while(~scanf("%s", s + 1)) {s[0] = '*';memset(dp, 0x3f, sizeof(dp));n = strlen(s);for(int i = 1; i <= 11; i ++) dp[i][0] = 0;for(int i = 1; i < n; i ++)sol(reid(s[i - 1]), reid(s[i]), i - 1);int ans = INF;for(int i = 1; i <= 6; i ++) ans = min(ans, dp[i][n - 1]);printf("%lld\n", ans + n - 1);}return 0;
}

MUV LUV EXTRA Time Limit: 2000/1500 MS (Java/Others) Memory Limit:
262144/262144 K (Java/Others) Total Submission(s): 0 Accepted
Submission(s): 0

Problem Description
鉴纯夏是一名成绩不太好的高中生。一天她在数学考试中碰到了一道求某条线段长度的问题。因为她并不会做这道题，所以她准确地作图后用尺子量出了这条线段的长度。不幸的是，答案在10进制下为一个无限小数，纯夏只量出了这个无限小数在10进制表示下的前若干位。

纯夏猜测问题的答案为一个有理数，所以答案为一个无限循环小数，如13=0.333⋯,3635=1.0285714285714⋯。纯夏希望从这个无限小数的前n位猜出原本的数字。纯夏意识到，猜测的循环节太长或循环节已经开始出现的部分长度太短是不可信的。举个例子，若她量出的小数为1.0285714285714，显然假设循环节为0285714285714（长度为13）或假设循环节为428571（已经开始出现的部分长度为7）都不如假设循环节为285714（长度为6，已经开始出现的部分长度为12）可靠。因此她定义一个循环节的可靠程度为a×循环节已经开始出现的部分长度−b×循环节长度。请你帮她求出最可靠的循环节的可靠程度为多少。

Input 第1行两个正整数a,b，含义如题目描述。

第2行一个字符串s表示纯夏量出的小数。

1≤a,b≤109

1≤|s|≤107

Hint

样例解释

对于第1组样例：

若猜测循环节为0，则可靠度=5×1−3×1=2；

其中，我们把以 0 为循环节的小数也看作无限循环小数。

若猜测循环节为20，则可靠度=5×2−3×2=4；

若猜测循环节为02，则可靠度=5×3−3×2=9；

若猜测循环节为020，则可靠度=5×3−3×3=6；

若猜测循环节为1020，则可靠度=5×4−3×4=8。

对于第2组样例：

若猜测循环节为2，则可靠度=2×1−1×1=1；

若猜测循环节为12，则可靠度=2×4−1×2=6；

若猜测循环节为21，则可靠度=2×3−1×2=4；

若猜测循环节为212，则可靠度=2×3−1×3=3；

若猜测循环节为1212，则可靠度=2×4−1×4=4。

注意，计算循环节可靠度的时候不考虑整数部分。输入中给出的整数部分只是为了还原纯夏见到的数字。

Output 一个整数表示最可靠的循环节的可靠程度。

怎么说啊没有想到有负数唉第一发就应该过的写的拓展KMP
过不去有推出了 KMP写法在然后发现是负数的问题第一发也能过
拓展KMP

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e7 + 5;
const int maxm = 1e6 + 5;
int n, m, cas;char s[maxn];
int z[maxn];void get_z() {int l = 0, r = 0;for(int i = l; i < n; i ++) {if(i > r) {l = i, r = i;while(r < n && s[r - l] == s[r]) r ++;z[i] = r - l, r --;} else {int k = i - l;if(z[k] < r - i + 1) z[i] = z[k];else {l = i;while(r < n && s[r - l] == s[r]) r ++;z[i] = r - l, r --;}}}
}signed main() {//ios::sync_with_stdio(false),cin.tie(0);long long a, b;while(~scanf("%lld %lld", &a, &b)) {scanf("%[^.]",s);getchar();scanf("%s", s);n = strlen(s);reverse(s, s + n);get_z();
//        for(int i = 0; i <= n; i ++) {
//            cout << z[i] << " ";
//        }cout << endl;int len = 1;long long ans = -INF;for(int i = 0; i < n; i ++) {if(z[i] == 0) {//cout << "0    "<< i + 1 << " " << i + 1<< endl;ans = max(ans, a * (i + 1) - b * (i + 1));} else {//   cout << "1     "<< i + z[i] << " " << i << endl;ans = max(ans, a * (i + z[i]) - b * (i));}}printf("%lld\n", ans);}return 0;
}

KMP

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e7 + 5;
const int maxm = 1e6 + 5;
int n, m, cas;char s[maxn];
int nxt[maxn];void get_z(){nxt[0] = -1;int i = 0, j = -1;while(i < n){if(j == -1 || s[j] == s[i]){i++, j++;nxt[i] = j;}else j = nxt[j];}
}signed main() {long long a, b;while(~scanf("%lld %lld", &a, &b)) {scanf("%s", s);n = strlen(s);int f = 0, t = 0;for(int i = 0; i < n; i ++) {if(s[i] == '.') {f = 1;continue;}if(f) s[t ++] = s[i];}s[t] = '\0';n = t;reverse(s, s + n);get_z();long long ans = -INF;for(int i = 1; i <= n; i ++) {ans = max(ans, i * a - b * (i - nxt[i]));}printf("%lld\n", ans);}return 0;
}