A
题意: 找出最小值之间最小的标号差
#include <bits/stdc++.h>
#define ll long long
#define N 100005
#define INF 0x3f3f3f3f
using namespace std;
typedef struct node{
ll vul;int x;
friend bool operator <(node aa,node bb){
if(aa.vul==bb.vul) return aa.x<bb.x;
return aa.vul<bb.vul;
}
}node;
node a[N];
int main(){
ios::sync_with_stdio(false);
int n;cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i].vul;a[i].x=i;}
sort(a+1,a+n+1);
int minn=INF;
for(int i=2;i<=n;i++){
if(a[i].vul!=a[i-1].vul) break;
minn=min(minn,a[i].x-a[i-1].x);
}
cout<<minn<<endl;
return 0;
}
B
题意：给你两块蛋糕分成n份 问怎么分使所有人蛋糕的最小值最大 要求 同一个人来的蛋糕只能来自同一份
#include <bits/stdc++.h>
using namespace std;
int n,a,b;
bool check(int mid){
int t=a/mid;int tt=b/mid;
if(t==0||tt==0) return false;
if(t+tt>=n) return true;
else return false;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>a>>b;
int l=1;int r=max(a,b);
int ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) {
ans=mid;l=mid+1;
}
else r=mid-1;
}
cout<<ans<<endl;
return 0;
}
C
题意：打表题 特判几种情况就行(证明可以通过数学归纳法证明
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int t1,t2,t3;cin>>t1>>t2>>t3;
if(t1==1||t2==1||t3==1){
cout<<"YES"<<endl;
}
else if(t1==3&&t2==3&&t3==3) cout<<"YES"<<endl;
else{
int cnt=0;
if(t1==2) cnt++;
if(t2==2) cnt++;
if(t3==2) cnt++;
int cnt1=0;
if(t1==4) cnt1++;
if(t2==4) cnt1++;
if(t3==4) cnt1++;
if(cnt>=2||(cnt1==2&&cnt==1)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
D
题意：问交换[l,r]区间的内的数后 整个区间的逆序对个数为奇数还是偶数
#include <bits/stdc++.h>
int a[1505];
using namespace std;
int main(){
ios::sync_with_stdio(false);
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[j]>a[i]) cnt++;
}
}
bool flag;
if(cnt%2) flag=1;
else flag=0;
int m;cin>>m;
int l,r;
//cout<<flag<<endl;
for(int i=1;i<=m;i++){
cin>>l>>r;
int t=(r-l+1)/2;
if(t%2){
if(flag==1) flag=0;
else flag=1;
}
if(flag) cout<<"odd"<<endl;
else cout<<"even"<<endl;
}
return 0;
}
E
题意：按题意模拟即可
#include <bits/stdc++.h>
#define N 400005
using namespace std;
stack<int>s;
int a[N],n,m,ans[N],x,y,cnt;
bool vis[N];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<=m;i++) vis[a[i]]++;
for(int i=1;i<=m;i++){
while(s.empty()||s.top()>a[i]) s.push(a[i]),i++;
if(i<=m){
while(!s.empty()&&s.top()<a[i]){
if(s.top()!=cnt+1){printf("-1
");return 0;}
ans[++cnt]=a[i];s.pop();
}
s.push(a[i]);
}
}
x=1;
cnt=m;
for(int i=1;i<=m;i++) ans[i]=a[i];
int flag=0;
while(cnt<n){
if(!s.empty()){
y=s.top();
for(int i=y;i>=x;i--) {
if(!vis[i])ans[++cnt]=i;}
x=y+1;s.pop();
}else{
for(int i=n;i>=x;i--) {
if(!vis[i])ans[++cnt]=i;}
if(cnt<n){printf("-1
");flag=1;break;}
}
}
if(flag==0){
for(int i=1;i<n;i++) printf("%d ",ans[i]);
printf("%d
",ans[n]);}
return 0;
}
F：
题解：构造一条直径(直径的构造 从任意一点出发找最远的点 然后从这个点找最远的点 这两个点就是直径的端点) 然后对于不在直径上点按照度进行删除即可
#include <bits/stdc++.h>
#define N 200005
#define ll long long
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
vector<int>vec[N];
vector<pair<int,int> >v;
int tt,mx_tt,t1,t2,n;
bool vis[N];
int dis[N],dis1[N];int fa[N],fa1[N];
stack<int>s1;stack<int>s2;
int du[N];
void dfs(int u,int pre,int dep){
if(tt<dep){
tt=dep;mx_tt=u;
}
for(int i=0;i<vec[u].size();i++){
if(vec[u][i]!=pre){
dfs(vec[u][i],u,dep+1);
}
}
}
void bfs(int t){
queue<int>que;que.push(t);
fa[t]=-1;
memset(dis,0,sizeof(dis));
while(!que.empty()){
int p=que.front();que.pop();
for(int i=0;i<vec[p].size();i++){
if(vec[p][i]!=fa[p]){
fa[vec[p][i]]=p;
dis[vec[p][i]]=dis[p]+1;
que.push(vec[p][i]);
}
}
}
tt=-1;
for(int i=1;i<=n;i++){
if(tt<dis[i]){
tt=dis[i];t2=i;
}
}
int ttt=t2;
while(ttt!=-1){
vis[ttt]=1;
ttt=fa[ttt];
}
return ;
}
void bfs2(int t){
queue<int>que;que.push(t);
memset(dis1,0,sizeof(dis1));
fa1[t]=-1;
while(!que.empty()){
int p=que.front();que.pop();
for(int i=0;i<vec[p].size();i++){
if(vec[p][i]!=fa1[p]){
dis1[vec[p][i]]=dis1[p]+1;
fa1[vec[p][i]]=p;
que.push(vec[p][i]);
}
}
}
return ;
}
int main(){
//ios::sync_with_stdio(false);
n=read();
for(int i=1;i<n;i++){
t1=read();t2=read();
vec[t1].push_back(t2);
vec[t2].push_back(t1);
du[t1]++;du[t2]++;
}
tt=-1;
dfs(1,-1,1);
t1=mx_tt;
bfs(t1);
bfs2(t2);
queue<int>que;
for(int i=1;i<=n;i++){
if(vis[i]==0&&du[i]==1) que.push(i);
}
//cout<<t1<<" "<<t2<<endl;
ll ans=0;
while(!que.empty()){
int p=que.front();que.pop();
ans+=max(dis[p],dis1[p]);
if(dis[p]>=dis1[p]){
v.push_back(make_pair(t1,p));
}
else v.push_back(make_pair(t2,p));
for(int i=0;i<vec[p].size();i++){
du[vec[p][i]]--;
if(du[vec[p][i]]==1&&vis[vec[p][i]]==0) que.push(vec[p][i]);
}
}
int ttt=t2;
while(fa[ttt]!=-1){
ans+=dis[ttt];
v.push_back(make_pair(t1,ttt));
ttt=fa[ttt];
}
printf("%I64d
",ans);
for(int i=0;i<v.size();i++){
//cout<<v[i].first<<" "<<v[i].second<<" "<<v[i].second<<endl;
printf("%d %d %d
",v[i].first,v[i].second,v[i].second);
}
return 0;
}
G
#include <bits/stdc++.h>
#define N 200005
using namespace std;
typedef struct node{
int cnt[101];
}node;
node d[N*6];
int vis[N];
int n,m;
int t1,t2;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
void push(int root){
for(int i=1;i<101;i++){
d[root<<1].cnt[i]=d[root].cnt[d[root<<1].cnt[i]];
d[root<<1|1].cnt[i]=d[root].cnt[d[root<<1|1].cnt[i]];
}
for(int i=1;i<101;i++) d[root].cnt[i]=i;
}
void built(int root,int l,int r){
push(root);
if(l==r){
return ;
}
int mid=(l+r)>>1;
built(root<<1,l,mid);
built(root<<1|1,mid+1,r);
}
void update(int root,int l,int r,int l1,int r1,int t,int e){
if(l<=l1&&r1<=r){
for(int i=1;i<101;i++){
if(d[root].cnt[i]==t) d[root].cnt[i]=e;
}
return ;
}
int mid=(l1+r1)>>1;
push(root);
if(l<=mid) update(root<<1,l,r,l1,mid,t,e);
if(r>mid) update(root<<1|1,l,r,mid+1,r1,t,e);
}
void querty2(int root,int l,int r){
if(l==r){
if(d[root].cnt[vis[l]]!=vis[l]) vis[l]=d[root].cnt[vis[l]];
return ;
}
int mid=(l+r)>>1;
push(root);
querty2(root<<1,l,mid);
querty2(root<<1|1,mid+1,r);
}
int main(){
n=read();
int ch,ch1;
for(int i=1;i<=n;i++){
ch=read();
vis[i]=ch;
}
built(1,1,n);int l,r;
m=read();
for(int i=1;i<=m;i++){
l=read();r=read();ch=read();ch1=read();
update(1,l,r,1,n,ch,ch1);
}
querty2(1,1,n);
for(int i=1;i<=n;i++){
if(i==1) printf("%d",vis[i]);
else printf(" %d",vis[i]);
}
// puts("");
return 0;
}