AtCoder Beginner Contest 378题解
总体情况
十分钟翻盘局。
A - Pairing
题意
有四个球,每次可以消掉两个颜色相同的球,问最多能效多少次?
题解
直接使用贪心即可
代码
// Problem: A - Pairing
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
namespace gtx{
// Fast IO
void read(int &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void read(char &x){do{x=getchar();}while(x==' '||x=='\n'||x=='\r');}
void write(char x){putchar(x);}
void write(int x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(int x,char y){write(x);write(y);}
#ifndef int
void read(long long &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void write(long long x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(long long x,char y){write(x);write(y);}
#endif
signed main(){
int a,b,c,d;
read(a);read(b);read(c);read(d);
map<int,int> mp;
mp[a]++;mp[b]++;mp[c]++;mp[d]++;
int ans=0;
for(auto i:mp) ans += i.second/2;
write(ans);
return 0;
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T = 1;
// gtx::read(T);
while(T--) gtx::main();
return 0;
}
B - Garbage Collection
题意
问第一个大于等于 \(d_j\) 的满足 \(\equiv r_{t_j} (\mod q_{t_j})\) 的数是多少。
思路
直接使用公式 \((y-d_x-1)\div t_x+1)*t_x+d_x\) 就行。
代码:
代码
// Problem: B - Garbage Collection
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
namespace gtx{
// Fast IO
void read(int &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void read(char &x){do{x=getchar();}while(x==' '||x=='\n'||x=='\r');}
void write(char x){putchar(x);}
void write(int x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(int x,char y){write(x);write(y);}
#ifndef int
void read(long long &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void write(long long x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(long long x,char y){write(x);write(y);}
#endif
int t[200],d[200];
int n,q;
signed main(){
read(n);
for(int i = 1;i<=n;i++){
read(t[i]);read(d[i]);
}
read(q);
for(int i = 1;i<=q;i++){
int x,y;
read(x);read(y);
if(y<=d[x]) write(d[x],endl);
else write(((y-d[x]-1)/t[x]+1)*t[x]+d[x],endl);
}
return 0;
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T = 1;
// gtx::read(T);
while(T--) gtx::main();
return 0;
}
C - Repeating
题意
求前面最后一个等于 \(a_i\) 的数。
思路
直接使用 map 即可。
代码
代码
// Problem: C - Repeating
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
namespace gtx{
// Fast IO
void read(int &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void read(char &x){do{x=getchar();}while(x==' '||x=='\n'||x=='\r');}
void write(char x){putchar(x);}
void write(int x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(int x,char y){write(x);write(y);}
#ifndef int
void read(long long &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void write(long long x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(long long x,char y){write(x);write(y);}
#endif
signed main(){
map<int,int> mp;
int n;
read(n);
for(int i = 1;i<=n;i++){
int x;
read(x);
if(mp.find(x)==mp.end()) write(-1,' ');
else write(mp[x],' ');
mp[x] = i;
}
return 0;
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T = 1;
// gtx::read(T);
while(T--) gtx::main();
return 0;
}
D - Count Simple Paths
题意
给你一个图,有.
和#
构成,求所有的简单路径。
思路
看这样样例 3 的答案便知满足的方案不多(我居然看了将近 1 个小时),考虑爆搜。
代码
代码
// Problem: D - Count Simple Paths
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
namespace gtx{
// Fast IO
void read(int &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void read(char &x){do{x=getchar();}while(x==' '||x=='\n'||x=='\r');}
void write(char x){putchar(x);}
void write(int x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(int x,char y){write(x);write(y);}
#ifndef int
void read(long long &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void write(long long x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(long long x,char y){write(x);write(y);}
#endif
const int MAXN = 15;
int n,m,k;
char a[MAXN][MAXN];
int f[MAXN][MAXN][MAXN][MAXN][MAXN];
void makeedge(int x,int y,int x1,int y1){
if(x1<1) return;
if(y1<1) return;
if(x1>n) return;
if(y1>m) return;
if(a[x1][y1]=='#') return;
f[x][y][x1][y1][1]++;
}
bool vis[MAXN][MAXN];
void count(int x,int y,int t);
void check(int x1,int y1,int t){
if(x1<1) return;
if(y1<1) return;
if(x1>n) return;
if(y1>m) return;
if(a[x1][y1]=='#') return;
if(vis[x1][y1]) return;
count(x1,y1,t);
}
int ans;
void count(int x,int y,int t){
if(t>k){
ans++;
return;
}
vis[x][y] = 1;
check(x+1,y,t+1);
check(x-1,y,t+1);
check(x,y+1,t+1);
check(x,y-1,t+1);
vis[x][y] = 0;
}
signed main(){
read(n);read(m);read(k);
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
read(a[i][j]);
}
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(a[i][j]=='#') continue;
count(i,j,1);
}
}
write(ans);
return 0;
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T = 1;
// gtx::read(T);
while(T--) gtx::main();
return 0;
}
E - Mod Sigma Problem
题意
给你一个由 \(N\) 个非负整数组成的序列 \(A = (A_1, A_2, \dots, A_N)\) 和一个正整数 \(M\) 。
求下列数值:
\[\sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right). \]这里, \(X \mathbin{\mathrm{mod}} M\) 表示非负整数 \(X\) 除以 \(M\) 的余数。
思路
首先考虑定一求一。我们可以按照左端点从右往左扫。
每一次扫都是新加一个集合,然后对所有集合加一个 \(A_i\)。
我们可以记一个偏移量。
每一次都是对已有的一些集合加集合元素个数个偏移量。
然而对有的数可能加上偏移量后大于 \(M\)。不难想到这些数都大于等于 \(M-\Delta\)。
于是考虑使用 FHQ_treap。
代码
// Problem: E - Mod Sigma Problem
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
namespace gtx{
// Fast IO
void read(int &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void read(char &x){do{x=getchar();}while(x==' '||x=='\n'||x=='\r');}
void write(char x){putchar(x);}
void write(int x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(int x,char y){write(x);write(y);}
#ifndef int
void read(long long &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void write(long long x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(long long x,char y){write(x);write(y);}
#endif
const int MAXN = 3e5+10;
int n,m,p,tot,ans,u,a[MAXN],sum[MAXN],j[MAXN];
struct node{
int ls,rs,id,sz,sum,pri;
}tree[MAXN];
#define lson tree[k].ls
#define rson tree[k].rs
void pushup(int k){
tree[k].sz = tree[lson].sz+tree[rson].sz+1;
tree[k].sum = tree[lson].sum+tree[rson].sum+tree[k].id;
}
void split(int k,int c,int &x,int &y){
if(!k){
x = y = 0;
return;
}
if(tree[k].id<=c){
x = k;
split(rson,c,rson,y);
}else{
y = k;
split(lson,c,x,lson);
}
pushup(k);
}
void split_rank(int k,int c,int &x,int &y){
if(!k){
x = y = 0;
return;
}
if(tree[lson].sz+1<=c){
x = k;
split_rank(rson,c-tree[lson].sz-1,rson,y);
}else{
y = k;
split_rank(lson,c,x,lson);
}
pushup(k);
}
int merge(int x,int y){
if(!x||!y) return x|y;
if(tree[x].pri<tree[y].pri){
tree[x].rs = merge(tree[x].rs,y);
pushup(x);
return x;
}else{
tree[y].ls = merge(x,tree[y].ls);
pushup(y);
return y;
}
}
mt19937 rd;
int sm,root;
int New_node(int x){
sm++;
tree[sm].pri = rd();
tree[sm].id = x;
tree[sm].sum = x;
tree[sm].sz = 1;
return sm;
}
void Insert(int x){
int lroot,rroot;
split(root,x,lroot,rroot);
root = merge(merge(lroot,New_node(x)),rroot);
}
void Delete(int x){
int lroot,temp,rroot;
split(root,x,lroot,rroot);
split(lroot,x-1,lroot,temp);
temp = merge(tree[temp].ls,tree[temp].rs);
root = merge(merge(lroot,temp),rroot);
}
int kth(int k){
int lroot,rroot,temp;
split_rank(root,k,lroot,rroot);
split_rank(lroot,k-1,lroot,temp);
int ans = tree[temp].id;
root = merge(merge(lroot,temp),rroot);
return ans;
}
int Rank(int x){
int lroot,rroot,ans;
split(root,x-1,lroot,rroot);
ans = tree[lroot].sz;
root = merge(lroot,rroot);
return ans;
}
int Pre(int x){
int lroot,rroot,ans;
split(root,x-1,lroot,rroot);
int now = lroot;
while(tree[now].rs) now = tree[now].rs;
ans = tree[now].id;
root = merge(lroot,rroot);
return ans;
}
int Suc(int x){
int lroot,rroot,ans;
split(root,x,lroot,rroot);
int now = rroot;
while(tree[now].ls) now = tree[now].ls;
ans = tree[now].id;
root = merge(lroot,rroot);
return ans;
}
int dlt;
int get(){
int sum = tree[root].sum+dlt*tree[root].sz;
int lroot,rroot;
split(root,m-dlt-1,lroot,rroot);
sum -= tree[rroot].sz*m;
root = merge(lroot,rroot);
return sum;
}
signed main(){
read(n);read(m);
for(int i = 1;i<=n;i++){
read(a[i]);
a[i]%=m;
sum[i] = sum[i-1]+a[i];
}
for(int l = n;l;l--){
dlt+=a[l];dlt%=m;
Insert(((-dlt+a[l])%m+m)%m);
// cout << dlt << " " << ((-dlt+a[l])%m+m)%m << " " << get() <<endl;
ans += get();
}
write(ans);
return 0;
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T = 1;
// gtx::read(T);
while(T--) gtx::main();
return 0;
}
F - Add One Edge 2
题意
一棵树上问加一条边,问使得形成的环为简单路径,且环上每个点的度数多为 3 的方案数。
思路
还剩二十多分钟,读题+想了 7 多分钟,打了 10 多分,极限翻盘。
首先分为两种情况:
- 一个点与根节点相连形成环,要求:根节点读数为 2,这个点的度数亦为 2,在这条路径上的其他店的度数为 3。
- 一个点经过根节点与另外一个子树形成环,要求:根节点度数为 3,这两个点度数为 2,其余为 3。
根据这两个情况,我们可以轻松得到一个状态:\(f_k\) 表示从 \(k\) 节点起,向下走若干个 3 节点最后抵达 2 节点的方案数。
转移很简单,这里就不说了。
于是。。。就做完了。
注意---Notise**:要减去一个节点为 2,且父节点度数也为 2 的情况。
代码
// Problem: F - Add One Edge 2
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
namespace gtx{
// Fast IO
void read(int &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void read(char &x){do{x=getchar();}while(x==' '||x=='\n'||x=='\r');}
void write(char x){putchar(x);}
void write(int x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(int x,char y){write(x);write(y);}
#ifndef int
void read(long long &x){
x = 0;int h = 1;char tmp;
do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
x*=h;
}
void write(long long x){
if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
do{st[++tot]=x%10,x/=10;} while(x);
while(tot){putchar(st[tot--]+'0');}
}
void write(long long x,char y){write(x);write(y);}
#endif
const int MAXN = 2e5+10;
int n,f[MAXN],f2[MAXN],d[MAXN],ans;
vector<int> v[MAXN];
void dfs(int k,int fath){
int sum = 0;
for(int i:v[k]){
if(i==fath) continue;
dfs(i,k);
if(d[k]==2){
ans += f[i]-(d[i]==2);
}else if(d[k]==3){
ans += f[i]*sum;
sum += f[i];
f[k] += f[i];
}
}
if(d[k]==2) f[k] = 1;
}
signed main(){
read(n);
for(int i = 1;i<n;i++){
int a,b;read(a);read(b);
v[a].push_back(b);
v[b].push_back(a);
d[a]++;d[b]++;
}
dfs(1,0);
write(ans);
return 0;
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T = 1;
// gtx::read(T);
while(T--) gtx::main();
return 0;
}