VP赛况如下：
前言：感觉这一场题目难度还是比较贴近新生的，我一个codeforces小蓝名一小时居然AK了,F题数据有点水(?)暴力dfs居然都能过...
A：A?C
题意：给你字符串，如果字符串是ABC，那么就输出ARC；反之输出ABC。
#include<bits/stdc++.h> using namespace std; int main(){ string a;cin>>a; if(a[1]=='R') cout<<"ABC"<<endl; if(a[1]=='B') cout<<"ARC"<<endl; }
B:Trick or Treat
题意：给你n个数，k个组，每组有d个数，然后输入d个数，标记，最后查找有[1,n]中有几个数字没被访问过
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; bool vis[maxn]; int main(){ int n,k;cin>>n>>k; for(int i=1;i<=k;i++){ int x;cin>>x; for(int j=1;j<=x;j++){ int q;cin>>q; vis[q]=true; } } int cnt=0; for(int i=1;i<=n;i++){ if(!vis[i]) ++cnt; } cout<<cnt<<endl; }
C：Peaks
题意:有N个观测台，M条边，每个人有一个高度H，输出有多少个节点满足它比所有它相邻的观测台高。
解法:我习惯用链式前向星来存边，思路就是查找每个节点的边，看是否>=他，如果是的话，那就不行了，否则ans++；
#include<bits/stdc++.h> #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int h[maxn]; int tot,head[maxn]; struct E{ int to,next; }edge[maxn<<1]; void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int main(){ int n,m;cin>>n>>m;mem(head,-1); for(int i=1;i<=n;i++) cin>>h[i]; for(int i=1;i<=m;i++){ int u,v;cin>>u>>v; add(u,v);add(v,u); } int ans=0; for(int u=1;u<=n;u++){ int flag=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(h[v]>=h[u]){ flag=1;break; } } if(!flag) ++ans; } cout<<ans<<endl; }
D:I hate Factorization
题意：给定X，输出一组(A，B)，满足A5-B5=X.
解法：看了一下数据范围，直接枚举暴力就行(写wa四次，一个小地方没开LL，好菜啊.....逃)
#include<bits/stdc++.h> #define ll long long using namespace std; int main(){ ll x;cin>>x; for(ll i=-1000;i<=1000;i++){ for(ll j=-1000;j<=1000;j++){ ll a=i*i*i*i*i;ll b=j*j*j*j*j; if(x==(a-b)){ cout<<i<<" "<<j<<endl; return 0; } } } }
E:This Message Will Self-Destruct in 5s
题意：给一个长度为N的序列A，求有多少数字对（i，j）满足Ai+Aj=|i - j|。
思路：我不太会数论..想了一会才明白。原式等价于：Aj + j = i - Ai，那么只需要每次查询 i - Ai的个数，然后更新Ai + i即可。
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=2e5+5; int a[maxn]; int main(){ int n;cin>>n; map<int,int> mp;ll ans=0; for(int i=1;i<=n;i++){ int x;cin>>x; ans+=mp[i-x]; mp[i+x]++; } cout<<ans<<endl; }
F: Three Variables Game
题意：给N个字符串（"AB","AC","BC"）和A,B,C三个值，按顺序执行每个字符串的操作，如果这个字符串是"AB"，那么将执行A--,B++或A++,B--，其它字符串类似，并且每一个操作之后A,B,C三个值不能小于0，判断是否按顺序执行下来，如是，并要求具体操作序列。
解法：看到这个题，第一反应就是dfs，配套剪枝就行(本来想想先莽一发dfs，但没想到过了，Exe_time也只有33ms，怀疑数据有点水？)
#include<bits/stdc++.h> #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int n,a,b,c; string s[maxn]; vector<char> vec; int flag; void dfs(int x,int a,int b,int c){ if(flag) return ; if(x==n+1&&a>=0&&b>=0&&c>=0){ flag=1; puts("Yes"); for(int i=0;i<n;i++) cout<<vec[i]<<endl; return ; } if(s[x][0]=='A'&&s[x][1]=='B'){ if(a+1>=0&&b-1>=0&&c>=0){ vec.push_back('A'); dfs(x+1,a+1,b-1,c); vec.pop_back(); } if(a-1>=0&&b+1>=0&&c>=0){ vec.push_back('B'); dfs(x+1,a-1,b+1,c); vec.pop_back(); } } else if(s[x][0]=='A'&&s[x][1]=='C'){ if(a+1>=0&&b>=0&&c-1>=0){ vec.push_back('A'); dfs(x+1,a+1,b,c-1); vec.pop_back(); } if(a-1>=0&&b>=0&&c+1>=0){ vec.push_back('C'); dfs(x+1,a-1,b,c+1); vec.pop_back(); } } else if(s[x][0]=='B'&&s[x][1]=='C'){ if(a>=0&&b-1>=0&&c+1>=0){ vec.push_back('C'); dfs(x+1,a,b-1,c+1); vec.pop_back(); } if(a>=0&&b+1>=0&&c-1>=0){ vec.push_back('B'); dfs(x+1,a,b+1,c-1); vec.pop_back(); } } } int main(){ cin>>n>>a>>b>>c;flag=0; for(int i=1;i<=n;i++) cin>>s[i]; dfs(1,a,b,c); if(!flag) puts("No"); }