又被薄纱了,rk就不放了,好丢人QwQ
Dashboard - Codeforces Round 756 (Div. 3) - Codeforces
A. Make Even
小分类讨论
题意:
给定一个数,每次操作可以选取其前缀然后翻转其前缀,问你最少操作几次可以把该数变为偶数
思路:
对次数分类讨论即可
如果本来就是偶数,就是0次
如果s[1]是偶数,翻转一整个就行
如果没有偶数位,就是-1
其余都是两次
Code:
#include <bits/stdc++.h>
//#define int long long
#define LL long long
const int mxn=1e6+10;
const int mxe=2e5+10;
const int mod=1e9+7;
using namespace std;string s;
void solve(){s.clear();cin>>s;int n=s.size();s=" "+s;if((s[n]-'0')%2==0) cout<<0<<'\n';else if((s[1]-'0')%2==0) cout<<1<<'\n';else{int ok=0;for(int i=1;i<=n;i++){if((s[i]-'0')%2==0) ok=1;}if(ok) cout<<2<<'\n';else cout<<-1<<'\n';}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;//p_init(1e6);while(__--)solve();return 0;
}
B. Team Composition: Programmers and Mathematicians
贪心
题意:
有a个数学家和b个计算机学家,4个人一组组队,每组至少包含两种学科,问最多能组几队
谢谢,不会小学数学
思路:
要使队伍数尽可能多,就让少的那个学科每队派一人,然后和另一个队组队
那么答案就是min(min(a,b),(a+b)/4)
Code:
#include <bits/stdc++.h>
//#define int long long
#define LL long long
const int mxn=1e6+10;
const int mxe=2e5+10;
const int mod=1e9+7;
using namespace std;int a,b;
void solve(){cin>>a>>b;cout<<min(min(a,b),(a+b)/4)<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;//p_init(1e6);while(__--)solve();return 0;
}
C. Polycarp Recovers the Permutation
构造+排列
题意:
思路:
一开始写了一小时的双指针模拟操作,然后写了一坨错了
这是构造题,考虑将一些一般条件特殊化,一般来说这种一般条件都是比较难处理的,像之前过年那会有个子序列,它就直接选了一整个序列,对于这种难处理的一般条件,我们考虑将其特殊化
注意到答案的排列(即原来的排列)的两端一定是最大值,否则就是无解
这道题就是把 双指针每次选小的那个 这个条件 转化成 固定一个指针动另一个,固定的那个指针大小一定为n,直接将其翻转即可
Code:
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define close(); ios::sync_with_stdio(false);
#define endl '\n'
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define dwn(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
int a[N];
int b[N];
void solve()
{int n; cin >> n;rep(i, 1, n) cin >> a[i];if(a[1] == n || a[n] == n){dwn(i, n, 1) cout << a[i] << " "; cout << endl;}else cout << -1 << endl;}int main()
{close();int T; cin >> T;while(T--) solve();// system("pause");
}
F. ATM and Students
尺取法
题意:
找出最长的连续子串使得其前缀和+s>=0
思路:
尺取法模板题,这道题居然有*1800,逆
Code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=2e5+10;int n,s;
int a[mxn],sum[mxn];
void solve(){memset(sum,0,sizeof(sum));cin>>n>>s;for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];int ans=-1,ansl,ansr;for(int l=1,r=1;l<=n;l++){while(r<=n&&sum[r]-sum[l-1]>=-s) r++;r--;if(ans<r-l+1){ans=r-l+1;ansl=l;ansr=r;}}if(ans==-1||ansl>ansr) cout<<-1<<'\n';else cout<<ansl<<" "<<ansr<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}
D. Weights Assignment For Tree Edges
构造
题意:
给定一棵树
又给了一个排列,对于p[i]满足dis[p[i]]>dis[p[i-1]]
dis是该结点的树上前缀和,w是边权
要你给这棵树的边权w赋值,使得能满足p排列的条件
思路:
模拟一下样例发现,我们可以遍历p[i]排列,把边权变成公差为1 的等差数列(特殊化边权)
如果父亲结点在p[i]中出现的id大于结点i,那么父亲结点的dis必然小于结点i,矛盾,所以这种情况无解
否则就去递推出p[i]的dis和w
Code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=2e5+10;int n,rt;
int fa[mxn],w[mxn],dis[mxn],id[mxn],p[mxn];
void solve(){memset(dis,0,sizeof(dis));memset(w,0,sizeof(w));cin>>n;for(int i=1;i<=n;i++){cin>>fa[i];if(fa[i]==i) rt=i;}for(int i=1;i<=n;i++){cin>>p[i];id[p[i]]=i;}if(p[1]!=rt) cout<<-1<<'\n';else{int ok=1;for(int i=2;i<=n;i++){if(id[p[i]]<id[fa[p[i]]]) ok=0;w[p[i]]=dis[p[i-1]]+1-dis[fa[p[i]]];dis[p[i]]=dis[fa[p[i]]]+w[p[i]];}if(!ok) cout<<-1<<'\n';else{for(int i=1;i<=n;i++) cout<<w[i]<<" \n"[i==n];}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}
E1. Escape The Maze (easy version)
BFS
题意:
有一棵树,Vlad和n个朋友玩游戏,Vlad位于节点1,n个朋友位于其他节点,第i个朋友位于xi。每个时刻,每个人都能沿着树边到达另一个点,或者留在原地。如果Vlad到达叶子节点,则Vlad赢。如果在其到达叶子前和其他人碰面(叶子也不能有其他人),则Vlad输。问最少需要保留多少个人能够保证Vlad输,即选取朋友的一个最小的子集,使得Vlad不能赢。
思路:
直接去BFS模拟过程,一格格染色,如果能把叶子结点染成1就是赢
Code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=2e5+10;
const int mxe=2e5+10;
struct ty{int to,next;
}edge[mxe<<1];
queue<int> q;int n,k,u,v;
int tot=0,ok=0;
int x[mxn],d[mxn],head[mxn],mark[mxn],vis[mxn];
void add(int u,int v){edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void init(){tot=0;ok=0;for(int i=0;i<=n;i++){x[i]=0;head[i]=-1;d[i]=0;mark[i]=0;vis[i]=0;}
}
bool bfs(){for(int i=1;i<=k;i++) q.push(x[i]),vis[x[i]]=1;q.push(1);vis[1]=1;mark[1]=1;while(!q.empty()){int u=q.front();q.pop();if(d[u]==1&&mark[u]==1&&u!=1) ok=1;for(int i=head[u];~i;i=edge[i].next){if(vis[edge[i].to]) continue;vis[edge[i].to]=1;q.push(edge[i].to);mark[edge[i].to]=mark[u];}}return ok;
}
void solve(){cin>>n>>k;init();for(int i=1;i<=k;i++) cin>>x[i];for(int i=1;i<=n-1;i++){cin>>u>>v;add(u,v);add(v,u);d[v]++;d[u]++;}//for(int i=1;i<=n;i++) if(d[i]==1) cout<<i<<'\n';if(bfs()) cout<<"YES"<<'\n';else cout<<"NO"<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}