掉大分力（悲
A - ^{-1}
直接模拟。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
using namespace std;
int n,a[200005],x,ans;
signed main(){
IOS;TIE;
cin>>n>>x;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==x) ans=i;
}
cout<<ans<<endl;
return 0;
}
B - Playing Cards Validation
直接判断即可。判重的话搞个 \(\text{map}\) 就好。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
using namespace std;
int n,fl;
map<string,bool> mp;
string s;
signed main(){
IOS;TIE;
cin>>n;
while(n--){
cin>>s;
if(mp[s]) fl=1;
mp[s]=1;
if(s[0]!='H'&&s[0]!='D'&&s[0]!='C'&&s[0]!='S'){
fl=1;
}
if(s[1]!='A'&&s[1]!='J'&&s[1]!='Q'&&s[1]!='K'&&s[1]!='T'&&!(s[1]>='2'&&s[1]<='9')){
fl=1;
}
}
cout<<(fl?"No":"Yes")<<endl;
return 0;
}
C - Ladder Takahashi
考虑用 \(\text{map}\) 进行离散化，同时记下每个楼层离散化之前的值，然后就可以建图跑 \(\text{DFS}\) 了。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
using namespace std;
int n,u,v,ans=1,tot=1,val[200005];
map<int,int> mp;
vector<int> a[200005];
bool vis[200005];
void dfs(int x){
for(int i=0;i<a[x].size();i++){
int tmp=a[x][i];
if(!vis[tmp]){
ans=max(ans,val[tmp]);
vis[tmp]=1;
dfs(tmp);
}
}
}
signed main(){
IOS;TIE;
cin>>n;
mp[1]=1;
for(int i=1;i<=n;i++){
cin>>u>>v;
if(!mp[u]) mp[u]=++tot,val[tot]=u;
if(!mp[v]) mp[v]=++tot,val[tot]=v;
a[mp[u]].push_back(mp[v]);
a[mp[v]].push_back(mp[u]);
}
vis[1]=1;
dfs(1);
cout<<ans<<endl;
return 0;
}
D - Takahashi's Solitaire
实际上就是求排序后最大连续整数段和。但是有一个取模的条件，也就是说可以是 \(m-2,m-1,0,1,2,\dots\) 这样的一段，所以考虑复制一遍排序后的数组。同时末尾放一个未出现数，防止最后一段取不到。设这样求出的最大连续整数段和为 \(mx\)，原先所有数之和为 \(sum\)，则最后答案为 \(\max(0,sum-mx)\)。和 \(0\) 取 \(\max\) 是为了防止整段形成一个环，使得有些数取了两次。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
using namespace std;
int n,a[400005],m,sum;
signed main(){
IOS;TIE;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
sort(a+1,a+n+1);
int tmp=0,mx=0;
a[0]=a[1];
for(int i=n+1;i<=n*2;i++) a[i]=a[i-n];
a[n*2+1]=-1;
for(int i=1;i<=n*2+1;i++){
if(a[i]==a[i-1]||a[i]==(a[i-1]+1)%m) tmp+=a[i];
else{
mx=max(mx,tmp);
tmp=a[i];
}
}
cout<<max(sum-mx,0ll)<<endl;
return 0;
}
E - Crystal Switches
考虑当成普通的 \(\text{BFS}\) 求最短路来做。不同之处在于，边是否可走与当前开关状态有关。想到，每个点在一种状态下应当只被访问一次，因为相同状态多次访问情况会变得相同。所以只需要把原先的 \(vis\) 数组改成二维，记 \(vis_{0/1,i}\) 表示边为 \(0/1\) 状态时是否更新过 \(i\)。所以在 \(\text{BFS}\) 的队列中也要再加入一个参数 \(now\) 表示当前状态。
设初始状态为 \(0\)，\(k.to\) 为当前队首，\(k.now\) 为当前队首状态，\(tmp.fl\) 为走向某一条边的初始状态，\(mark_i\) 为点 \(i\) 是否有开关，则有：
- 若 \(k.now\oplus tmp.fl=1\)，可以不更改状态更新
- 否则，若 \(mark_{k.to}=1\)，可以更改状态更新
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
using namespace std;
int n,m,k,s,u,v,t,ans=1e18;
bool mark[200005],vis[2][200005];
struct node{
int to,fl;
};
vector<node> a[200005];
struct Node{
int to,ans,now;
};
queue<Node> q;
signed main(){
IOS;TIE;
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
cin>>u>>v>>t;
a[u].push_back({v,t});
a[v].push_back({u,t});
}
for(int i=1;i<=k;i++) cin>>s,mark[s]=1;
vis[0][1]=1;
q.push({1,0,0});
while(q.size()){
Node k=q.front();q.pop();
if(k.to==n){
cout<<k.ans<<endl;
return 0;
}
for(int i=0;i<a[k.to].size();i++){
node tmp=a[k.to][i];
if(k.now^tmp.fl){
if(!vis[k.now][tmp.to]){
vis[k.now][tmp.to]=1;
q.push({tmp.to,k.ans+1,k.now});
}
}
else if(mark[k.to]){
if(!vis[k.now^1][tmp.to]){
vis[k.now^1][tmp.to]=1;
q.push({tmp.to,k.ans+1,k.now^1});
}
}
}
}
cout<<-1<<endl;
return 0;
}
咕咕咕
标签：AtCoder,int,题解,cin,long,mp,277,tie,define From： https://www.cnblogs.com/binary1110011/p/16884829.html