目录
A - Three Threes
输入一个数n，输出n个n.
B - Pentagon
给定一个正五边形，任意给两对顶点，问这两对顶点之间的距离是否相同，因为字母给定，可以打表，也可以思考一下：两对顶点差值的绝对值是否相等或者是否加和为5
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin()+1,a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef pair<int,int>pii;
const int N =7;
signed main()
{IOS
string a,b;cin>>a>>b;
if(abs(a[0]-a[1])==abs(b[0]-b[1])||abs(a[0]-a[1])==5-abs(b[0]-b[1]))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
C - Repunit Trio
每一位都是1的数叫做 repunit ,问第N小的 由三个 repunit 数组合的数是多少，数据很小,直接暴力+set去重即可
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef pair<int,int>pii;
signed main()
{IOS
int w[13]={
1,
11,
111,
1111,
11111,
111111,
1111111,
11111111,
111111111,
1111111111,
11111111111,
111111111111,
1111111111111
};
set<int>ans;
for(int i=0;i<13;i++){
for(int j=0;j<13;j++){
for(int k=0;k<13;k++){
ans.insert(w[i]+w[j]+w[k]);
}
}
}
int n;cin>>n;
auto its= next(ans.begin(),n-1);
cout<<*its<<endl;
return 0;
}
D - Erase Leaves
对于以1为根的数，每次可以删除一次树的叶子节点，问最少几次可以删除到1
要想删除1，那么必须让1为叶子节点，设1有n个子树(n>0)也就是说必须删除n-1个以1为根的子树 ，为了使得操作数最小，我们留下结点最多的子树，我们通过使用DFS遍历获取子树和，并且更新最大子树的节点数，最终得出结果
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef pair<int,int>pii;
const int N =3e6+7;
int e[N],ne[N],h[N],idx,mas;
bool st[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int p){
st[p]=1;
int sum=1;
for(int i=h[p];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]){
int x=dfs(j);
sum+=x;
mmax(mas,x);
}
}
return sum;
}
signed main()
{IOS
int n;cin>>n;
int p=n;
memset(h,-1,sizeof h);
while(p--)
{
int a,b;cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1);
cout<<n-mas<<endl;
return 0;
}
E - Takahashi Quest
遇到1是药水，2是怪物，可以收集药水放进背包，如果遇到怪物可以消耗药水击杀怪物，如果遇到怪物且没有药水 则游戏结束，在保证游戏能够不结束的情况下，做到背包容量最小，如果一定会结束，输出-1；
我们假设先将所有药水全都收集，然后再根据遇到的怪物来更新是否用该药水，如果无当前怪物对应药水，则输出-1，否则，在最后根据遇到的怪物更新背包容量
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef pair<int,int>pii;
signed main()
{IOS
int n;cin>>n;
vct<int>a(n+1),b(n+1);
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
vct<vct<int>>v(n+1);
vct<int>st(n+1);
bool isok=1;
for(int i=1;i<=n;i++){
if(a[i] == 1) {
v[b[i]].pb(i);
} else {
if(v[b[i]].empty()) {
isok=0;break;
}
st[v[b[i]].back()]=1;
v[b[i]].pop_back();
}
}
if(!isok)cout<<"-1"<<endl;
else {
int t=0,ans=0;
for(int i=1;i<=n;i++){
if(a[i]==1) {
if(st[i]==1)t++;
mmax(ans,t);
} else t--;
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)if(a[i]==1)cout<<"01"[st[i]]<<" ";
}
return 0;
}
