比赛
A - Four Digits
打印一个四位数，位数不够补0
思路：把每一位抠出来，计算它的位数，计算长度和4的差值，设插值位d，打印d个0，然后再打印这个数即可
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iostream>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define rep1(c,a,b) for(int c = a;c < b;++c)
#define rep2(c,a,b) for(int c = a;c >= b;--c)
#define repx(a,b) for(int a = h[b];~a;a = ne[a])
#define mfx(h) memset(h,-1,sizeof h);
#define mf1(h) memset(h,0,sizeof h);
#define mf2(h) memset(h,0x3f,sizeof h);
#define mf3(h) memset(h,-ox3f,sizeof h);
#define ALL(a) a.begin(),a.end()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
template <class T> T mod(T a,T b){return (a % b + b) % b;}
const int N = 110,M = 22,K = 110;
const int MOD18 = 1e8,INF = 0x3f3f3f3f;
const double eps = 1e-8;
int n,k1,k2;
int g[N],c[N];
int main(){
scanf("%d",&n);
VI nums;
while (n)nums.pb(n % 10),n /= 10;
int div = 4 - nums.size();
rep1(i,0,div)printf("0");
rep2(i,nums.size() - 1,0)printf("%d",nums[i]);
return 0;
}
B - Failing Grade
n个学生n个成绩，设p为合格成绩，计算不合格的人数
思路：暴力枚举即可
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iostream>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define rep1(c,a,b) for(int c = a;c < b;++c)
#define rep2(c,a,b) for(int c = a;c >= b;--c)
#define repx(a,b) for(int a = h[b];~a;a = ne[a])
#define mfx(h) memset(h,-1,sizeof h);
#define mf1(h) memset(h,0,sizeof h);
#define mf2(h) memset(h,0x3f,sizeof h);
#define mf3(h) memset(h,-ox3f,sizeof h);
#define ALL(a) a.begin(),a.end()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
template <class T> T mod(T a,T b){return (a % b + b) % b;}
const int N = 110,M = 22,K = 110;
const int MOD18 = 1e8,INF = 0x3f3f3f3f;
const double eps = 1e-8;
int n,k1,k2,m;
int g[N],c[N];
int main(){
scanf("%d%d",&n,&m);
int res = 0;
rep1(i,0,n){
int c;
scanf("%d",&c);
if(c < m)res++;
}
printf("%d",res);
return 0;
}
C - Swiss-System Tournament
2n个玩家进行石头剪刀布的游戏，一共进行m次比赛，每一轮比赛的每一场为1和2 2和3 ...以此类推
每轮结束，按获胜次数排序，相同的次数按编号从小到大排序
思路：暴力，每一轮结束，进行排序，排序规则自定义。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iostream>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define rep1(c,a,b) for(int c = a;c < b;++c)
#define rep2(c,a,b) for(int c = a;c >= b;--c)
#define repx(a,b) for(int a = h[b];~a;a = ne[a])
#define mfx(h) memset(h,-1,sizeof h);
#define mf1(h) memset(h,0,sizeof h);
#define mf2(h) memset(h,0x3f,sizeof h);
#define mf3(h) memset(h,-ox3f,sizeof h);
#define ALL(a) a.begin(),a.end()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
template <class T> T mod(T a,T b){return (a % b + b) % b;}
const int N = 110,M = 22,K = 110;
const int MOD18 = 1e8,INF = 0x3f3f3f3f;
const double eps = 1e-8;
int n,m;
PII q[N];
char match[N][N];
int check(char a,char b){
//printf("%c %c \n",a,b);
if(a == 'G' && b == 'C')return 1;
if(a == 'C' && b == 'P')return 1;
if(a == 'P' && b == 'G')return 1;
if(a == 'G' && b == 'G')return -1;
if(a == 'C' && b == 'C')return -1;
if(a == 'P' && b == 'P')return -1;
return 0;
}
bool cmp(PII a,PII b){
if(a.fi > b.fi)return true;
if(a.fi < b.fi)return false;
if(a.se < b.se)return true;
return false;
}
int main(){
scanf("%d%d",&n,&m);
rep1(i,1,2 * n + 1)q[i] = {0,i};
rep1(i,1,2 * n + 1){
rep1(j,1,m + 1){
cin >> match[i][j];
}
}
rep1(i,1,m + 1){
rep1(j,1,2 * n + 1){
int a = q[j].se;
int b = q[j + 1].se;
int ret = check(match[a][i],match[b][i]);
if (ret == 1)q[j].fi = q[j].fi + 1;
if(ret == 0)q[j + 1].fi = q[j + 1].fi + 1;
j++;
}
sort(q + 1,q + 1 + 2 * n,cmp);
}
rep1(i,1,2 * n + 1)printf("%d\n",q[i].se);
return 0;
}
D - Between Two Arrays
给两个个非递减的序列：
a = {a1,a2,a3,a4,...,an}
b = {b1,b2,b3,b4,...,bn}
构造c
使得 ai <= ci <= bi
思路：观察ai,ai+1 和 bi bi+1，ci+1的取值为ai+1 ~ bi+1，那么以ci+1结束的非递减序列的个数就是取决于ci，即在ai~bi中寻找<=ci+1的情况，可以考虑使用dp，设f[i] [j]为前i个数构造，且ci为j的个数，那么 f[i] [j] = f[i] [j] + f[i - 1] [k];(k <= j)
TLE做法：
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iostream>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define rep1(c,a,b) for(int c = a;c < b;++c)
#define rep2(c,a,b) for(int c = a;c >= b;--c)
#define repx(a,b) for(int a = h[b];~a;a = ne[a])
#define mfx(h) memset(h,-1,sizeof h);
#define mf1(h) memset(h,0,sizeof h);
#define mf2(h) memset(h,0x3f,sizeof h);
#define mf3(h) memset(h,-ox3f,sizeof h);
#define ALL(a) a.begin(),a.end()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
template <class T> T mod(T a,T b){return (a % b + b) % b;}
const int N = 3010,M = 22,K = 110;
const int MOD18 = 1e8,INF = 0x3f3f3f3f;
const double eps = 1e-8;
int n,m;
LL f[N][N];
int a[N],b[N];
int main(){
scanf("%d",&n);
rep1(i,1,n + 1)scanf("%d",&a[i]);
rep1(i,1,n + 1)scanf("%d",&b[i]);
rep1(i,0,3001)f[0][i] = 1;
rep1(i,1,n + 1){
int st = a[i],ed = b[i];
rep1(j,st,ed + 1){
rep1(k,a[i - 1],j + 1){
if(k > b[i - 1])continue;
f[i][j] = (f[i][j] + f[i - 1][k]) % 998244353;
}
//printf("%d %d %d \n",i,j,f[i][j]);
}
}
LL res = 0;
rep1(i,a[n],b[n] + 1)res = (res + f[n][i]) % 998244353;
printf("%lld",res);
return 0;
}
对TLE进行优化，第三层循环维护一个变量就可以了
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iostream>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define rep1(c,a,b) for(int c = a;c < b;++c)
#define rep2(c,a,b) for(int c = a;c >= b;--c)
#define repx(a,b) for(int a = h[b];~a;a = ne[a])
#define mfx(h) memset(h,-1,sizeof h);
#define mf1(h) memset(h,0,sizeof h);
#define mf2(h) memset(h,0x3f,sizeof h);
#define mf3(h) memset(h,-ox3f,sizeof h);
#define ALL(a) a.begin(),a.end()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
template <class T> T mod(T a,T b){return (a % b + b) % b;}
const int N = 3010,M = 22,K = 110;
const int MOD18 = 1e8,INF = 0x3f3f3f3f;
const double eps = 1e-8;
int n,m;
LL f[N][N];
int a[N],b[N];
int main(){
scanf("%d",&n);
rep1(i,1,n + 1)scanf("%d",&a[i]);
rep1(i,1,n + 1)scanf("%d",&b[i]);
int nextst = a[2];
LL sum = 0;
rep1(i,a[1],b[1] + 1){
f[1][i] = 1;
if(i < nextst)sum = (sum + f[1][i]) % 998244353;
}
rep1(i,2,n + 1){
LL st = a[i],ed = b[i] + 1;
nextst = a[i + 1];
LL cnt = 0;
rep1(j,st,ed){
sum = (sum + f[i - 1][j]) % 998244353;
f[i][j] = (f[i][j] + sum) % 998244353;
if(j < nextst)cnt = (cnt + f[i][j]) % 998244353;
}
sum = cnt;
}
LL res = 0;
rep1(i,a[n],b[n] + 1)res = (res + f[n][i]) % 998244353;
printf("%lld",res);
return 0;
}
补题
E - Red and Blue Tree
思路：
R - B = k
设ci为每个边通过的次数,S = c1 + c2 + c3 + cn-1
那么R + B = S
解得：R = (k + S) / 2
即可转化为一个01背包求方案数的问题
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iostream>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define rep1(c,a,b) for(int c = a;c < b;++c)
#define rep2(c,a,b) for(int c = a;c >= b;--c)
#define repx(a,b) for(int a = h[b];~a;a = ne[a])
#define mfx(h) memset(h,-1,sizeof h);
#define mf1(h) memset(h,0,sizeof h);
#define mf2(h) memset(h,0x3f,sizeof h);
#define mf3(h) memset(h,-ox3f,sizeof h);
#define ALL(a) a.begin(),a.end()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
template <class T> T mod(T a,T b){return (a % b + b) % b;}
const int N = 1010,M = N * 2,K = 110;
const int MOD18 = 1e8,INF = 0x3f3f3f3f,MOD = 998244353;
const double eps = 1e-8;
int n,m,k;
int h[N],e[M],ne[M],w[M],idx;
int root[N];//save the move
int sum[N];
int f[100010];
void add(int a,int b,int c){
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
//count the sum of vertices
int dfs(int b,int u,int fa){
if(u == b)return 1;
repx(i,u) {
int j = e[i];
if (j == fa)continue;
int c = dfs(b, j,u);
if(c){
//printf("%d ---\n",w[i]);
sum[w[i]]++;
return 1;
}
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
rep1(i,1,m + 1)scanf("%d",&root[i]);
mfx(h);
rep1(i,1,n){
int a,b;
scanf("%d%d",&a,&b);
add(a,b,i);
add(b,a,i);
}
rep1(i,1,m)dfs(root[i + 1],root[i],-1);
int s = 0;
rep1(i,1,n){
s += sum[i];
//printf("%d ",sum[i]);
}
//puts("");
//
if((s + k) % 2 || s + k < 0){
cout << 0;
return 0;
}
//dp
f[0] = 1;
rep1(i,1,n){
rep2(j,100000,sum[i]){
f[j] = (f[j] + f[j - sum[i]]) % MOD;
}
}
//printf("11");
printf("%d",f[(s + k) / 2]);
return 0;
}
F - Expensive Expens
思路：官方题解很牛逼。利用了树的直径，将每个点的结果范围进行缩小。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iostream>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define rep1(c,a,b) for(int c = a;c < b;++c)
#define rep2(c,a,b) for(int c = a;c >= b;--c)
#define repx(a,b) for(int a = h[b];~a;a = ne[a])
#define mfx(h) memset(h,-1,sizeof h);
#define mf1(h) memset(h,0,sizeof h);
#define mf2(h) memset(h,0x3f,sizeof h);
#define mf3(h) memset(h,-ox3f,sizeof h);
#define ALL(a) a.begin(),a.end()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<LL,LL> PLL;
typedef pair<double,double> PDD;
template <class T> T mod(T a,T b){return (a % b + b) % b;}
const int N = 200010,M = N * 2,K = 110;
const int MOD18 = 1e8,INF = 0x3f3f3f3f,MOD = 998244353;
const double eps = 1e-8;
int n,m,k;
int h[N],e[M],ne[M],idx;
LL w[M];
bool st[N];
LL val[N];
LL d1[N];
LL d2[N];
LL d3[N];
LL d4[N];
void add(int a,int b,LL c){
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void dijkstr(LL d[],int start){
mf1(st);
d[start] = 0;
priority_queue<PLL,vector<PLL>,greater<PLL>> q;
q.push({d[start],start});
while (q.size()){
auto t = q.top();
q.pop();
int u = t.se;
LL distance = t.fi;
if(st[u])continue;
st[u] = true;
repx(i,u){
int j = e[i];
if(d[j] > distance + w[i]){
d[j] = distance + w[i];
q.push({d[j],j});
}
}
}
}
int main(){
scanf("%d",&n);
mf2(d1);
mf2(d2);
mf2(d3);
mf2(d4);
mfx(h);
rep1(i,1,n){
int a,b;LL c;cin >> a >> b >> c;
add(a,b,c);
add(b,a,c);
}
rep1(i,1,n + 1)cin >> val[i];
int s = 1,t = -1,u = -1;//find diameter
dijkstr(d1,s);//d1
LL cost = -1;
rep1(i,1,n + 1){
if (i == s)continue;
if(val[i] + d1[i] > cost){
cost = val[i] + d1[i];
t = i;
}
}
//printf("-->%d\n",t);
//find another
dijkstr(d2,t);//d1
cost = -1;
rep1(i,1,n + 1){
if(i == t)continue;
if(val[i] + d2[i] > cost){
cost = val[i] + d2[i];
u = i;
}
}
//printf("-->%d\n",u);
//find diameter over
dijkstr(d3,t);//d3
dijkstr(d4,u);//d4
//rep1(i,1,n + 1)printf("%d\t",d3[i]);
//puts("");
rep1(i,1,n + 1){
LL cost = -1;
if(i != t)cost = max(cost,d3[i] + val[t]);
if(i != u)cost = max(cost,d4[i] + val[u]);
cout << cost << endl;
}
return 0;
}
G H 不会
5555~
