对于想了解ValidateInternationalPhoneNumbers(验证国际电话号码)的读者，本文将提供新的信息，我们将详细介绍国际手机号验证码，并且为您提供关于193.ValidPhone
对于想了解Validate International Phone Numbers (验证国际电话号码)的读者，本文将提供新的信息，我们将详细介绍国际手机号验证码，并且为您提供关于193. Valid Phone Numbers、940C Phone Numbers、ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...、ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...的有价值信息。
本文目录一览：- Validate International Phone Numbers (验证国际电话号码)（国际手机号验证码）
- 193. Valid Phone Numbers
- 940C Phone Numbers
- ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...
- ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...
Validate International Phone Numbers (验证国际电话号码)（国际手机号验证码）
正则表达式：
\+(?:\d ?){6,14}\d
eg:
+86 573 265 1630111
193. Valid Phone Numbers
Given a text file file.txt that contains list of phone numbers (one per line),write a one liner bash script to print all valid phone numbers.
You may assume that a valid phone number must appear in one of the following two formats: (xxx) xxx-xxxx or xxx-xxx-xxxx. (x means a digit)
You may also assume each line in the text file must not contain leading or trailing white spaces.
Example:
Assume that file.txt has the following content:
987-123-4567 123 456 7890 (123) 456-7890
Your script should output the following valid phone numbers:
987-123-4567 (123) 456-7890
# Read from the file file.txt and output all valid phone numbers to stdout.
egrep ‘(^\([0-9]{3}\) |^[0-9]{3}-)[0-9]{3}-[0-9]{4}$‘ file.txt
940C Phone Numbers
传送门
题目大意
给你两个数字n和k，给你一个字符串s，n是s的长度，求字母集合是s的字母集合子集的字典序大于s的长度为k的字典序最小的字符串t
分析
将字符转化为数字，然后分两种情况处理：
1.n<k:t的前n为是s，后面几位是s中字典序最小的字母
2.n>=k:将t赋为s的前k位，从t的最后一位开始，如果字符子集中有字典序比它大的则将其替换为比其大的中字典序最小的字符，否则将其替换为整个字符子集中字典序最小的字符，在此位的前一位重复此步骤
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
char s[110000],t[110000];
bool is[50];
int a[110000],b[110000],c[50];
int n,m,j,k,cnt=0;
inline void gob(int pl){
if(b[pl-1]<c[cnt]){
for(int i=1;i<=cnt;i++)
if(c[i]>b[pl-1]){
b[pl-1]=c[i];
return;
}
}
else {
b[pl-1]=c[1];
gob(pl-1);
}
}
int main()
{ int i;
cin>>n>>k;
scanf("%s",s+1);
for(i=1;i<=n;i++){
a[i]=s[i]-''a'';
if(!is[a[i]])c[++cnt]=a[i];
is[a[i]]=1;
}
sort(c+1,c+1+cnt);
for(i=1;i<=min(n,k);i++){
b[i]=a[i];
}
if(k>n){
for(i=n+1;i<=k;i++)b[i]=c[1];
}
else {
if(is[b[k]+1]){
b[k]+=1;
}
else if(b[k]<c[cnt]){
for(i=1;i<=cnt;i++)
if(c[i]>b[k]){
b[k]=c[i];
break;
}
}
else {
b[k]=c[1];
gob(k);
}
}
for(i=1;i<=k;i++)
t[i]=(b[i]+''a'');
printf("%s",t+1);
return 0;
}
ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...
签到题
A
4min 1Y
C
45min 3Y
题意
给两个串，要把第一个串变成第二个串。每次选择一个半径r，然后以第一个串的中心为中心，r为半径，左右翻转。问最少几次操作？
题解
细节有点多。
- 先是输出
-1的情况。这个很好考虑 - 然后遍历s1串，对于位置
i，如果需要翻转(s1[i]=s2[n+1-i])，则打上标记1，不需要翻转(s1[i]=s2[i]).则打上标记0，如果翻不翻转都可以(s1[i]=s1[n+1-i])，打上标记2。 - 遍历
[1,n/2]，对于打上标记2的位置，我们要决定是翻还是不翻，根据贪心，我们可以怠惰一点！对于打上标记2的位置，和前一个位置保持一致即可。
F
25min 1Y
题解
统计一下每个数字出现了多少次，出现了x次，对答案的贡献则为x!，相乘即为答案。
J
42min 2Y
题解
按题意模拟。
冷静分析一下开局
- 开场看了C觉得很基本，然后过了A，开始写C。
- C细节没考虑清楚，用了
10min，WA on test 2!
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100000 + 10;
int T;
char s1[N], s2[N], s3[N];
bool ok[N];
int main() {
scanf("%d", &T);
while (T --) {
scanf("%s %s", s1+1, s2+1);
int n = strlen(s1+1);
int mid = (n+1)/2;
if (s1[mid] != s2[mid]) {
printf("-1\n"); continue;
}
bool gg = 0;
for (int i=1;i<mid;i++) {
if (s1[i]==s2[i] && s1[n-i+1]==s2[n-i+1])
ok[i] = 1;
else if (s1[i]==s2[n-i+1] && s1[n-i+1]==s2[i])
ok[i] = 0;
else
gg = 1;
}
if (gg) {
printf("-1\n"); continue;
}
int ans = 0;
ok[0] = 1;
for(int i=1;i<mid;i++) {
if (ok[i] != ok[i-1])
ans ++;
}
printf("%d\n", ans);
}
}
完全没有考虑s1[i]=s1[n+1-i]的情况。
用了6分钟fix了一下。s1[i]=s1[n+1-i]
int ans = 0;
ok[0] = 1;
for(int i=1;i<mid;i++) {
if (ok[i] != ok[i-1] && ok[i] != 2)
ans ++;
}
printf("%d\n", ans);
然后喵了个呜，又一次WA2
- 我逃跑，用了5min时间过了F
- 用了10min的时间J题
WA2 - 用了5min的时间fix了一下，人调换方向那个地方写得意识有点模糊。
- 用了2min时间fix了一下C，很沙比的错误，比如说
n = 7,前3位，标记为0 2 0的情况就智障掉了。
前期比较容易细节没考虑清楚就上去写代码。C,J这两个模拟题都是这个原因吧。开始写代码之间，大概是抱着“随便搞搞就好”的想法。这种态度很沙比的啊。
- 我在求什么？
- 在模拟的过程，变量会如何变化？
这两个问题都考虑得不清楚吧！
中档题
B
Hash的做法很容易看出。然后就unlimited WA TLE MLE
搞Hash的经验严重不足？
边的种数不会超过n种，因此我们放n个桶。每个桶记录这种边出现的次数。
然后就是对一个XXX进制下，n位数的hash了【双hash保平安】
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int N = 10000008;
const LL MOD1 = 100000007;
const LL MOD2 = 923439347;
int T;
int n, x, y;
int val[N]; vector<int> v;
LL k1[N], k2[N];
unordered_map< LL, int > mp;
int main() {
scanf("%d", &T);
k1[0] = k2[0] = 1;
for(int i=1;i<N;i++) {
k1[i]=k1[i-1]*10007LL%MOD1;
k2[i]=k2[i-1]*20007LL%MOD2;
}
while (T --) {
scanf("%d", &n);
v.clear();
for (int i = 1; i <= n; i ++) {
scanf("%d %d", &x, &y);
if (x > y) swap(x, y);
val[i] = (2*n+1)*x + y;
v.push_back(val[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i=1;i<=n;i++) {
val[i] = lower_bound(v.begin(), v.end(), val[i])-v.begin()+1;
}
mp.clear();
LL sum1, sum2;
LL ans=0;
for (int i=1;i<=n;i++) {
sum1 = 0, sum2 = 0;
for(int j=1;j<=n;j++) {
sum1 += k1[val[j]];
sum1 %= MOD1;
sum2 += k2[val[j]];
sum2 %= MOD2;
}
mp[sum1*MOD2 + sum2] ++;
for(int j=i+1;j<=n;j++) {
sum1 += k1[val[j]]-k1[val[j-i]];
sum1 = (sum1%MOD1+MOD1)%MOD1;
sum2 += k2[val[j]]-k2[val[j-i]];
sum2 = (sum2%MOD2+MOD2)%MOD2;
mp[sum1*MOD2+sum2] ++;
}
for (auto x: mp) {
LL v = x.second;
ans += v * (v - 1) / 2;
}
mp.clear();
}
printf("%lld\n", ans);
}
}
G
题意
修改最少的元素，使得序列的GCD为x，LCM为y。
题解
先判-1(一番激烈的讨论)
如果a[i]%x!=0 or y%a[i]!=0，那么i就是个卜。
直觉告诉我们把一个数字变成x,另一个数字变成y，只要其它的数字不卜，生活就有保障了。
- 如果卜的个数>=2,那么答案就是卜的个数了。
- 否则答案可能是1，可能是2，可能是0
- 答案是0，很简单。
- 答案是1，很不简单。我们枚举一下每个数字，看他是否能力挽狂澜，我们把枚举的数字放逐掉，求出其它数字的GCD&LCM(先预处理前缀后缀GCD&LCM)，然后看一看世界末日前怎么办？来得及拯救吗？【具体怎么做，留给读者思考。】
- 答案是2，很简单，加个else
I
题意
n堆石头，两种操作，两人轮流操作。
- 可以从一堆石头中拿走一个石头。
- 如果每堆石子都至少有1个，可以从每堆石头中拿走一个石头。
先手胜？后手胜？
题解
冷静分析一下
- n%2=1. 易证，留给读者思考【读者似乎就我一个人。】
- n%2=0. 这个得冷静分析一下。
- min=1, 先手可以把后手气死。类似于chomp Game的模型。
- min=2, 第一种操作肯定不可以施展的！不然会被气死。既然只能施展第二种操作，胜负显而易见了吧。
- min=3, 先手可以把后手气死。类似于chomp Game的模型。
- min=4, .......
博弈在模型的直觉很重要的吖！这题意识到了chomp Game就很简单了吧。
K
题意
n个点，n条边，多组查询，求两点间最短路。
题解
先去掉一条边edge，那么这个图就是一颗树了。
枚举，u到v是否要经过edge即可。
冷静分析一下中期
- 先用了10min施展G，施展了一大半，然后咕咕咕了。
- 先用了10min施展B题。没考虑清楚自己在hash什么东西，耽误了一段时间，然后
WA11。 - 用了13min过了K。
- 用了3min过了G的样例，
WA2 - 开始unlimited Fix G，中间用了很长一段时间次饭去了。但调G的时间至少有1小时。
- Bug1：没读完就输出结果，WA
- Bug2：复杂度
nsqrt(n).【不错，有创意】 - Bug3：
n=1的特判不到位，搞得后面越界了。一大波RE。
- 用了一个小时Fix B题的Hash，好不容易开始双hash然后MLE。枚举长度后清空，解决了问题。
- 用了半个小时搞I
emmmm....大部分时间都在Fix辣鸡。。。
考虑清楚再写啊······
羊肉粉丝汤弱鸡啊。
感觉30min 4题，2h30min8题是比较合理的。
ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...
A.Arcade Game（康拓展开）
题意：
给出一个每个数位都不同的数n，进行一场游戏。每次游戏将n个数的每个数位重组。如果重组后的数比原来的数大则继续游戏，否则算输。如果重组后的数是最大的数则算赢，问赢的概率。
题解：
用康拓展开求出n是第几大的数，然后递推后面的概率。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
char s[15];
double ans;
int fac[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
double cal(char *s) {
int res = 0;
int k = strlen(s);
for(int i = 0; i < k; i++) {
int cnt = 0;
for(int j = i+1; j < k; j++) if(s[j]<s[i]) cnt++;
res += fac[k-i-1]*cnt;
}
if(res==fac[k]-1) return 0;
double ans = 1.0/fac[k];
for(int i = res; i < fac[k]-2; i++) ans += ans/fac[k];
return ans;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%s", s);
printf("%.9lf\n", cal(s));
}
}
B.Unlucky Teacher（模拟）
题意：
Q个题目和M个学生的判卷，求出每道题的答案。如果求不出则输出？。
题解：
模拟即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int q, m;
int num[105], state[105];
char ans[105];
char s1[2], s2[2];
int main() {
scanf("%d", &t);
while(t--) {
memset(state, 0, sizeof(state));
memset(num, 0, sizeof(num));
scanf("%d%d", &q, &m);
while(m--) {
for(int i = 1; i <= q; i++) {
scanf("%s%s", s1, s2);
if(s2[0]==''T'') num[i] = -1, ans[i] = s1[0];
else {
if((num[i]==-1)||((state[i]&(1<<s1[0]-''A''))>0)) continue;
state[i] |= 1<<s1[0]-''A'';
num[i]++;
if(num[i]==3) {
for(int j = 0; j < 4; j++)
if(!(state[i]&(1<<j))) {
ans[i] = ''A''+j;
break;
}
num[i] = -1;
}
}
}
}
for(int i = 1; i <= q; i++) {
if(num[i]>-1) printf("?");
else printf("%c", ans[i]);
if(i < q) printf(" ");
}
puts("");
}
}
C.Connecting Graph（并查集+二分）
题意：
初始有n个点，m次操作。每次操作加一条边或者询问两个点第一次连通的时刻（若不连通输出-1）。
题解：
GYM - 100814 C.Connecting Graph
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int t;
int n, m;
int u, v, k;
int f[N], num[N];
vector<pair<int, int> > g[N];
vector<int> c[N];
bool check(int x) {
int l = 0, r = g[u].size()-1;
while(l <= r) {
int mid = l+r>>1;
if(g[u][mid].first <= x) l = mid+1;
else r = mid-1;
}
int p1 = g[u][r].second;
l = 0, r = g[v].size()-1;
while(l <= r) {
int mid = l+r>>1;
if(g[v][mid].first <= x) l = mid+1;
else r = mid-1;
}
int p2 = g[v][r].second;
if(p1==p2) return 1;
return 0;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
num[i] = 1;
f[i] = i;
c[i].clear();
g[i].clear();
c[i].push_back(i);
g[i].push_back(make_pair(0, i));
}
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &k, &u, &v);
if(k&1) {
u = f[u]; v = f[v];
if(u!=v) {
if(num[u]>num[v]) swap(u, v);
for(int j = 0; j < num[u]; j++) {
c[v].push_back(c[u][j]);
f[c[u][j]] = v;
g[c[u][j]].push_back(make_pair(i, v));
}
num[v] += num[u];
num[u] = 0;
c[u].clear();
}
}
else {
int l = 0, r = i-1;
while(l<=r) {
int mid = l+r>>1;
if(check(mid)) r = mid-1;
else l = mid+1;
}
if(check(r+1)) printf("%d\n", r+1);
else puts("-1");
}
}
}
}
D.Frozen Rivers
题意：
一棵n个节点的树，每条边代表一条河。从点1开始边以每秒1个单位开始融化。每个点连的边（不包括连向父亲的）有一条融化完时剩下的该点连的边融化速度降为0.5。q次询问，每次询问某个时刻融化到叶子节点的数量。
题解：
设minn[u]代表节点u的边中权值最小的那个，将点u所有边的权值加上他们与minn[u]的差值。即每条边的权值翻倍再减去minn[u]。
这样处理完之后就省去了0.5的限制。问题变成了求叶子节点到根节点的距离。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
int t;
int n, q, p, c;
int tot;
int head[N], to[N], nxt[N], w[N], minn[N];
int cnt;
ll tim, num[N];
void dfs(int u, ll val) {
if(minn[u]==inf) {
num[++cnt] = val;
return ;
}
for(int i = head[u]; ~i; i = nxt[i]) {
w[i] = 2*w[i]-minn[u];
dfs(to[i], val+w[i]);
}
}
int main() {
scanf("%d", &t);
while(t--) {
tot = cnt = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) head[i] = -1, minn[i] = inf;
for(int i = 2; i <= n; i++) {
scanf("%d%d", &p, &c);
to[++tot] = i; nxt[tot] = head[p]; head[p] = tot, w[tot] = c;
minn[p] = min(minn[p], c);
}
dfs(1, 0);
sort(num+1, num+cnt+1);
scanf("%d", &q);
while(q--) {
scanf("%lld", &tim);
int ans = upper_bound(num+1, num+cnt+1, tim)-num-1;
printf("%d\n", ans);
}
}
}
E.Palmyra（dp）
题意：
给出n*m的矩阵。从点（1，1）出发，可以向右或者向下移动，最后走到（n，m）。将路途上的点值乘起来，问最后的值拿6进制表示末尾最多有几个0。
题解：
题意可以理解为，使最后2的因子数和3的因子数中的最小值最大。
dp[i][j][k]表示走到（i，j），3的因子数为k时2的因子数最多是多少。
#include <bits/stdc++.h>
using namespace std;
int t;
int n, m;
int q[105][105][3];
int dp[105][105][1505];
int main() {
scanf("%d", &t);
while(t--) {
memset(q, 0, sizeof(q));
memset(dp, -1, sizeof(dp));
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &q[i][j][0]);
int t = q[i][j][0];
while(t%2 == 0) {
q[i][j][1]++;
t /= 2;
}
while(t%3 == 0) {
q[i][j][2]++;
t /= 3;
}
}
}
dp[1][1][q[1][1][2]] = q[1][1][1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int n2 = q[i][j][1];
int n3 = q[i][j][2];
for(int k = 0; k + n3 <= 1500; k++) {
if(dp[i][j-1][k] != -1)
dp[i][j][k+n3] = max(dp[i][j][k+n3], dp[i][j-1][k]+n2);
if(dp[i-1][j][k] != -1)
dp[i][j][k+n3] = max(dp[i][j][k+n3], dp[i-1][j][k]+n2);
}
}
}
int ans = 0;
for(int i = 1; i <= 1500; i++) {
int nn = min(dp[n][m][i], i);
ans = max(ans, nn);
}
printf("%d\n", ans);
}
return 0;
}
F.Geometry
题意：
给出长和宽，判断时正方形还是矩形。
题解：
判断w是否等于h。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int w, h;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &w, &h);
if(w==h) puts("Square");
else puts("Rectangle");
}
}
G.It is all about wisdom（最短路+二分）
题意：
给出一个图，图中的每条边有使用的最低限制值和花费。问从1走到n在总花费小于k的前提下的最小限制值是多少。
题解：
标准的二分套最短路的题型。二分最小的限制值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
int t;
int n, m, k;
int u, v, c, l, r;
int vis[N], dis[N];
struct node {
int to, v, lim;
node(int a, int b, int c) {
to = a; v = b; lim = c;
}
};
vector<node> g[N];
bool check(int x) {
queue<int> q;
for(int i = 1; i <= n; i++) vis[i] = 0, dis[i] = inf;
q.push(1);
vis[1] = 1;
dis[1] = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
vis[v] = 0;
int len = g[v].size();
for(int i = 0; i < len; i++) {
if(g[v][i].lim > x) continue;
if(g[v][i].v+dis[v] < dis[g[v][i].to]) {
dis[g[v][i].to] = g[v][i].v+dis[v];
if(!vis[g[v][i].to]) {
q.push(g[v][i].to);
vis[g[v][i].to] = 1;
}
}
}
}
if(dis[n] < k) return 1;
return 0;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &m, &k);
r = 0;
for(int i = 1; i <= n; i++) g[i].clear();
while(m--) {
scanf("%d%d%d%d", &u, &v, &c, &l);
g[u].push_back(node(v, c, l));
g[v].push_back(node(u, c, l));
r = max(r, l);
}
l = 1;
while(l<=r) {
int mid = l+r>>1;
if(check(mid)) r = mid-1;
else l = mid+1;
}
if(check(r+1)) printf("%d\n", r+1);
else puts("-1");
}
}
I.Salem
题意：
给出n个数，求数对中最大的hamming距离。
题解：
每两个数求一下异或之后二进制下1个数量即可，输出最大值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
int a[105];
int main() {
scanf("%d", &t);
while(t--) {
int ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
for(int j = 1; j < i; j++) {
int p = a[i]^a[j], cnt = 0;
for(int k = 20; k >= 0; k--) {
if(p&(1<<k)) cnt++;
}
ans = max(ans, cnt);
}
}
printf("%d\n", ans);
}
}
J.Game
题意：
给出合并规则表。两个人轮流进行操作，每次选择从最左面或者最右面开始每两个合并成一个。如果最后剩的是元音字符，就是Salah获胜。否则Marzo获胜。
题解：
暴力维护每一种情况。用1表示S获胜，0表示M获胜。
当S操作时，若两种情况存在1，则当前为1。
当M操作时，若两种情况存在0，则当前为0。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
int t;
int tot;
int len[N];
char s[N][N];
char g[30][30];
char cmp[5] = {''a'', ''e'', ''i'', ''o'', ''u''};
bool dfs(int num, int k) {
if(len[num] < 3) {
char c;
if(len[num]==1) c = s[num][0];
else c = g[s[num][0]-''a''][s[num][1]-''a''];
for(int i = 0; i < 5; i++) if(c==cmp[i]) return true;
return false;
}
++tot;
for(int i = 0; i < len[num]; i+=2) {
if(i==len[num]-1) s[tot][i/2] = s[num][i];
else s[tot][i/2] = g[s[num][i]-''a''][s[num][i+1]-''a''];
}
len[tot] = (len[num]+1)/2;
bool res = dfs(tot, k^1);
if(len[num]&1) {
++tot;
s[tot][0] = s[num][0];
for(int i = 1; i < len[num]; i+=2) {
s[tot][i/2+1] = g[s[num][i]-''a''][s[num][i+1]-''a''];
}
len[tot] = (len[num]+1)/2;
if(k) res &= dfs(tot, k^1);
else res |= dfs(tot, k^1);
}
return res;
}
int main() {
scanf("%d", &t);
while(t--) {
tot = 0;
for(int i = 0; i < 26; i++) scanf("%s", g[i]);
scanf("%s", s[0]);
len[0] = strlen(s[0]);
if(dfs(0, 0)) puts("Salah");
else puts("Marzo");
}
}
K.PhD math
题意：
给出a，b，n，p（a<b）。求a/b的前n位数中有多少字串整除p。
题解：
从1扫到n。维护每一位新增的余数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int t;
ll a, b;
int n, p;
int bit[N];
int v1[205], v2[205];
ll ans;
int main() {
scanf("%d", &t);
while(t--) {
ans = 0;
memset(v1, 0, sizeof(v1));
memset(v2, 0, sizeof(v2));
scanf("%lld%lld%d%d", &a, &b, &n, &p);
for(int i = 1; i <= n; i++) {
a *= 10;
bit[i] = a/b;
a = a%b;
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < p; j++) {
if(i&1) v1[j] = 0;
else v2[j] = 0;
}
for(int j = 0; j < p; j++) {
if(i&1) v1[(j*10+bit[i])%p] += v2[j];
else v2[(j*10+bit[i])%p] += v1[j];
}
if(i&1) v1[bit[i]%p]++, ans += v1[0];
else v2[bit[i]%p]++, ans += v2[0];
}
printf("%lld\n", ans);
}
}
L.Candy Jars（博弈）
题意：
N个罐子，每个罐子有一定数量的糖。两个人轮流操作，每次选定一罐，把其他罐中的糖都扔掉。然后把选定罐中的糖任意分配给每个罐，但要保证每个罐中都有糖。不能操作者判输。
题解：
只要有一个罐子糖数必胜则操作者必胜。
当所有罐子糖数小于N时无法给所有罐子分配糖，必输。
当存在罐子糖数在[N，N(N-1)]时，可以把糖分成必输态，即分成所有罐子糖数小于N的状态，这时必胜。
然后举例发现N(N-1)是一个循环节，取模就可以了。
#include <bits/stdc++.h>
using namespace std;
int t, n;
int k;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int ans = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &k);
k %= n*(n-1);
if(k==0 || k > n-1) ans = 1;
}
if(ans) puts("Alice");
else puts("Bob");
}
}
M.Building Force Fields（dp）
题意：
按x升序给出n个点的二维坐标，并保证没有两个点x坐标相同。可以在任意两个点之间连边，最后要保证每个点都在连边之下（或在连边上）。问最小的连边总长。
题解：
dp[i]表示第i个点结尾的最小总连边长。
转移是枚举i向第j（1<=j<i）个点连边，要保证连边上方无点。即第i和第j个点的斜率比第i个点和（j，i）范围内的点的斜率都小。最后取最小值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
double dp[1005];
struct node {
ll x, y;
}a[1005];
double dis(int n1, int n2) {
return sqrt((a[n1].x-a[n2].x)*(a[n1].x-a[n2].x)+(a[n1].y-a[n2].y)*(a[n1].y-a[n2].y));
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lld%lld", &a[i].x, &a[i].y);
dp[1] = dis(1, 2);
for(int i = 2; i <= n; i++) {
int pos = i-1;
dp[i] = min(dp[i-2], dp[i-1])+dis(i, i-1);
for(int j = i-2; j >= 1; j--) {
if((a[i].y-a[pos].y)*(a[i].x-a[j].x) >= (a[i].y-a[j].y)*(a[i].x-a[pos].x)) {
dp[i] = min(dp[i], min(dp[j-1], dp[j])+dis(i, j));
pos = j;
}
}
}
printf("%.6lf\n", dp[n]);
}
}
今天的关于Validate International Phone Numbers (验证国际电话号码)和国际手机号验证码的分享已经结束，谢谢您的关注，如果想了解更多关于193. Valid Phone Numbers、940C Phone Numbers、ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...、ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...的相关知识，请在本站进行查询。
本文标签：
![[转帖]Ubuntu 安装 Wine方法（ubuntu如何安装wine）](https://www.gvkun.com/zb_users/cache/thumbs/4c83df0e2303284d68480d1b1378581d-180-120-1.jpg)
