ABC378
光速切掉前四题，结果倒在了第五题。
A - Pairing
难度：红。
弱智题，不解释。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[5]={0};
for(int i=1;i<=4;i++){
int x;cin>>x;a[x]++;
}
int ans=0;
for(int i=1;i<=4;i++){
if(a[i]>=2&&a[i]<=3)ans++;
if(a[i]>=4)ans+=2;
}
cout<<ans;
return 0;
}
B - Garbage Collection
难度：红
弱智题，不解释。
#include<bits/stdc++.h>
#define ll long long
#define mxn 110
using namespace std;
ll n,q[mxn],r[mxn];
ll a,t,d;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>q[i]>>r[i];
cin>>a;
while(a--){
cin>>t>>d;
cout<<d+(r[t]-d%q[t]+q[t])%q[t]<<'\n';
}
return 0;
}
C - Repeating
难度：红
弱智题，不解释。
#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
using namespace std;
ll n;
map<ll,ll> mp;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
ll x;cin>>x;
if(mp[x])cout<<mp[x]<<' ';
else cout<<"-1 ";
mp[x]=i;
}
return 0;
}
D - Count Simple Paths
难度：橙
暴搜就行了，不解释。
#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
using namespace std;
ll h,w,kk,pos[4][2]={{0,1},{1,0},{0,-1},{-1,0}},ans;
char c[15][15];
bool vis[15][15];
void dfs(ll i,ll j,ll k){
if(i<1||i>h||j<1||j>w||c[i][j]=='#')return;
if(vis[i][j])return;
if(k==kk){
ans++;return;
}
vis[i][j]=1;
for(int x=0;x<4;x++)
dfs(i+pos[x][0],j+pos[x][1],k+1);
vis[i][j]=0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>h>>w>>kk;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
cin>>c[i][j];
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
dfs(i,j,0);
cout<<ans;
return 0;
}
E - Mod Sigma Problem
难度：黄-绿
首先，我们计算出前缀和 \(sum_i\) 和前缀和的前缀和 \(ssum_i\)。
设 \(ans_i\) 为以 \(i\) 为结尾的序列的和。
若无取模的话，则有 \(ans_i=(i+1)*sum_i-ssum_{i-1}\)。
但是现在有一个问题，取模。
我们让 \(sum_i\) 对 \(m\) 取模，注意这时 \(ssum\) 是不能取模的。
但是这会造成一个问题，取模后的 \(sum_i\) 可能小于 \(sum_{1\sim i-1}\)，也就是说会出现负数。
所以还要维护一下 \(sum_{1\sim i}\) 中比 \(sum_i\) 大的数的个数。
用什么树状数组，权值线段树都可以维护。
#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
using namespace std;
ll n,m,a[mxn],ans,sum[mxn],ssum[mxn],b[mxn];
namespace tree{
ll sum[mxn];
ll lowbit(ll x){
return x&-x;
}
void add(ll x,ll k){
while(x<=m)sum[x]+=k,x+=lowbit(x);
}
ll query(ll x){
ll ret=0;
while(x)ret+=sum[x],x-=lowbit(x);
return ret;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
sum[i]=(sum[i-1]+a[i])%m;
b[i]=tree::query(m)-tree::query(sum[i]+1);
tree::add(sum[i]+1,1);
}
for(int i=1;i<=n;i++)ssum[i]=(ssum[i-1]+sum[i]);
for(int i=1;i<=n;i++)ans+=(i*sum[i]+b[i]*m-ssum[i-1]);
cout<<ans;
return 0;
}
F - Add One Edge 2
难度：黄-绿
计算度数为 \(3\) 的连通块中相邻的度数为 \(2\) 的点的数量即可。
#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
#define pb push_back
using namespace std;
ll n,cnt,ans,vis[mxn],vis2[mxn],d[mxn];
vector<ll> t[mxn],g[mxn];
void dfs(int u){
vis[u]=1;
for(int i=0;i<t[u].size();i++){
int v=t[u][i];
if(d[v]==2&&!vis2[v])
vis2[v]=1,cnt++;
else if(d[v]==3&&!vis[v])
dfs(v);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
t[u].pb(v),t[v].pb(u);
d[u]++,d[v]++;
}
for(int i=1;i<=n;i++){
if(d[i]==3&&!vis[i]){
memset(vis2,0,sizeof(vis2));
cnt=0;
dfs(i);
ans+=cnt*(cnt-1)/2;
}
}
cout<<ans;
return 0;
}
G - Everlasting LIDS
难度：紫
由于这题太难了，所以咕着，先扔个复制过来的code。
#include<bits/stdc++.h>
#define vi vector<int>
#define ll long long
using namespace std;
ll n,m,P;
void DP(map<vi,ll> &dp){
for(auto bf:dp){
vi p=bf.first;
ll w=bf.second;
for(int i=0;i<n;i++){
if(p[i]<(i?p[i-1]:m)){
p[i]++;
dp[p]=(dp[p]+w)%P;
p[i]--;
}
}
}
}
map<vi,ll> dp1,dp2;
int main(){
cin>>n>>m>>P;
if(n>m)swap(n,m);
vi p(n);
dp1[p]=1,p[n-1]=1,dp2[p]=1;
DP(dp1),DP(dp2);
for(int i=0;i<n;i++)p[i]=m;
ll ans=dp1[p]*dp2[p]%P;
cout<<ans;
return 0;
}