A - Past ABCs
简单的枚举判断即可
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>
#define si set<int>
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
void solve()
{
string s;
cin>>s;
int sum=0;
for (int i=3;i<6;i++){
sum=sum*10+(s[i]-'0');
}
string s1=s.substr(0,3);
if(s1=="ABC" && sum>=1 && sum<=349 && sum!=316){
YES
}
else {
NO
}
}
signed main()
{
IOS
int t;
t=1;//cin>>t;
while(t--){
solve();
}
}B - Dentist Aoki
如果一个洞奇数次进，则总数加一偶数次进总数减一。
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>
#define si set<int>
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
void solve()
{
int n,q;
cin>>n>>q;
int sum=n;
vector<int> a(n+1,1);
for (int i=1;i<=q;i++){
int x;
cin>>x;
if(a[x]==1){
a[x]=0;
sum--;
}
else {
a[x]=1;
sum++;
}
}
cout<<sum;
}
signed main()
{
IOS
int t;
t=1;//cin>>t;
while(t--){
solve();
}
}C - Sort
先用一个数组记录第几个输入的数字，然后一个数组记录这个数字的位置，
然后再按照排列从小到大的顺序遍历，如果这个数不在相对应的位置上就和其需要到的位置上的数交换 。时间复杂度(n).
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>
#define si set<int>
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
void solve()
{
int n;
cin>>n;
vi a(n+1);
vi b(n+1);
for (int i=1;i<=n;i++){
cin>>a[i];
b[a[i]]=i;
}
int cnt=0;
vector<pi> v;
for (int i=1;i<=n;i++){
if(b[i]!=i){
int j=b[i];
swap(a[i],a[j]);
swap(b[a[i]],b[a[j]]);
v.push_back({i,j});
}
}
cout<<(int)v.size()<<endl;
for (int i=0;i<(int)v.size();i++){
auto [x,y]=v[i];
cout<<x<<" "<<y<<endl;
}
}
signed main()
{
IOS
int t;
t=1;//cin>>t;
while(t--){
solve();
}
}D - New Friends
这题考察联通块的知识，每个联通块内都可以有（cnt)*(cnt-1)/2条边。
这题可以用两种做法：
1.图论
因为存在一个点被联通块内多个点连接的情况，所以每次先加上边，最后除以2.
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>
#define si set<int>
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int vis[200010];
void solve()
{
int n,m;
cin>>n>>m;
vector<vector<int>> v(n+1);
for (int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
int ans=0;
for (int i=1;i<=n;i++){
if(vis[i]){
continue;
}
queue<int> q;
q.push(i);
vis[i]=1;
int cnt1=1,cnt2=0;
while(q.size()){
int u=q.front();
q.pop();
for (auto x : v[u]){
cnt2++;
if(vis[x]==0){
vis[x]=1;
cnt1++;
q.push(x);
}
}
}
ans+=cnt1*(cnt1-1)-cnt2;
}
ans/=2;
cout<<ans;
}
signed main()
{
IOS
int t;
t=1;//cin>>t;
while(t--){
solve();
}
}2.并查集
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>
#define si set<int>
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int p[200010],cnt[200010];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void solve()
{
int n,m;
cin>>n>>m;
iota(p+1,p+n+1,1);
for (int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
p[find(x)]=find(y);
}
int ans=-m;
for (int i=1;i<=n;i++){
cnt[find(i)]++;
}
for (int i=1;i<=n;i++){
ans+=cnt[i]*(cnt[i]-1)/2;
}
cout<<ans;
}
signed main()
{
IOS
int t;
t=1;//cin>>t;
while(t--){
solve();
}
}E - Toward 0
mp[n]是n的期望花费。
cost1=mp[n/a]+x。
cost2=1~6 mp[n/i] / 6 + y 当i=1时 两边有相同的式子，把它移到左边。
cost2=
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>
#define si set<int>
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
void solve()
{
int n,a,x,y;
cin>>n>>a>>x>>y;
map<int,double> mp;
auto dfs=[&](auto dfs,int u)-> double{
if(u==0){
return 0;
}
if(mp.find(u)!=mp.end()){
return mp[u];
}
double cost1=dfs(dfs,u/a)+x;
double cost2=0;
for (int i=2;i<=6;i++){
cost2+=dfs(dfs,u/i);
}
cost2=cost2/5+1.0*y*6/5;
return mp[u]=min(cost1,cost2);
};
dfs(dfs,n);
cout<<fixed<<setprecision(10)<<mp[n];
}
signed main()
{
IOS
int t;
t=1;//cin>>t;
while(t--){
solve();
}
}
