2020/7/30

Educational Codeforces Round 143 (Rated for Div. 2)\C_Tea_Tasting.cpp

//题意：有n种茶，n个人，第i种茶有 a[i]的量，第i个人一次能喝 b[i], 第i个人从第i种茶开始往前喝，求每个人最多能喝多少茶。

//思路：纯模拟时间超限，对于a数组中的每个元素，他要减的是包括i在内以及其右边的b数组中的元素，

//那么需要先求出b数组的前缀和数组sum，那么对于任意的ai,我们可以找到它从i向右减b中元素后第一次减成0的位置

//也就是在前缀和数组中从i向右的位置二分查找第一个sum[j]-sum[i-1]>ai的位置j，从i到j-1的每一个b中元素都是使ai减去一个完整的自己的，

//bj使ai减剩下的数减到了0，用差分数组cnt记录b中每个元素使a中元素减去了几个完整的自己也就是对于每次二分查找，都有cnt[i]++,cnt[j]--，

//然后用另一个数组ex记录b中每个数使a中某个数减到零所提供的贡献，n次二分查找结束后，对差分数组求前缀和，答案数组就等于cnt[i]*b[i]+ex[i]

#include<bits/stdc++.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<queue>#include<cstring>#include<math.h>#include<map>#include<vector>#include<stack>using namespace std;#define endl '\n'typedef pair<int,int> pr;#define int long long#define ll long long#define fr(i,l,r) for(int i=l;i<=r;i++)#define ufr(i,n,z) for(int i = n;i >= z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N = 1e6+10;const int mod=998244353,inf=LONG_LONG_MAX;int n,m;int a[N];int b[N];int sum[N];int ex[N];void solve(){/* cin>>n;fr(i,1,n){cin>>a[i];c[i]=0;}fr(i,1,n){cin>>b[i];}fr(i,1,n){ufr(j,i,1){c[i]+=min(a[j],b[i]);if(b[i]>=a[j]){a[j]=0;}else{a[j]-=b[i];}}}fr(i,1,n){cout<<c[i]<<' ';}cout<<'\n'; */int n;cin>>n;fr(i,1,n){cin>>a[i];sum[i]=0;ex[i]=0;}fr(i,1,n){int x;cin>>x;b[i]=b[i-1]+x;}fr(i,1,n){int it=upper_bound(b+1,b+1+n,b[i-1]+a[i])-b;         //后面的a不用减前面的b,整体基础上+b[i-1]//cout<<it<<' ';sum[i]++;sum[it]--;ex[it]+=a[i]-(b[it-1]-b[i-1]);}//cout<<'\n';fr(i,1,n){sum[i]+=sum[i-1];}fr(i,1,n){cout<<sum[i]*(b[i]-b[i-1])+ex[i]<<' ';}cout<<'\n';}signed main(){int t=1;cin>>t;while(t--) solve();return 0;}

Codeforces Round 887 (Div. 2)\C_Ntarsis_Set.cpp

//题意:n个数，每次按照顺序删除位于a[i]位置的这n个数，问k次后最小的是多少

//思路：如果没有1，则最小为1，有1通过列举情况可以发现对于某一个删除位，前面有几个删除位，后面就要跳几次删，

//于是发现这是一个公差为1，2,3...不断变化的n个数列，第i个数列截止与a[i+1],为了防止没有k个数，于是增加一个公差为n+1,截止于1e18的数列

#include<bits/stdc++.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<queue>#include<cstring>#include<math.h>#include<map>#include<vector>#include<stack>using namespace std;#define endl '\n'typedef pair<int,int> pr;#define int long long#define ll long long#define fr(i,l,r) for(int i=l;i<=r;i++)#define ufr(i,n,z) for(int i = n;i >= z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N = 1e6+10;const int mod=998244353,inf=LONG_LONG_MAX;int a[N];void solve(){int n,k;cin>>n>>k;fr(i,1,n){cin>>a[i];}if(a[1]!=1){cout<<1<<'\n';return;}a[n+1]=inf;                //保证一定有k个数vector<int>v;int cnt=1;int d=1;fr(i,2,n+1){while(cnt+d<a[i]){cnt+=d;v.push_back(cnt);if(v.size()>k+1){break;}}if(v.size()>k+1){break;}d=i;}cout<<v[k-1]<<'\n';}signed main(){int t=1;cin>>t;while(t--) solve();return 0;}

\Codeforces Round 842 (Div. 2)\C_Elemental_Decompress.cpp

//题意：给定一个长度为n的排列a，请构造两个数组 p,q，要求 max(pi,qi)=ai，并且两个数组都是排列，请输出两个数组。

//思路：1.对于出现三次及以上的NO,对于出现两次的一定有没出现出现的与之对应，否则NO

//2.将出现两次的与没出现的对应，没出现的记录，在记录寻找首次小于出现两次的对应，下一次再出现颠倒位置，

#include<bits/stdc++.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<queue>#include<cstring>#include<math.h>#include<map>#include<vector>#include<stack>using namespace std;#define endl '\n'typedef pair<int,int> pr;#define int long long#define ll long long#define fr(i,l,r) for(int i=l;i<=r;i++)#define ufr(i,n,z) for(int i = n;i >= z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N = 1e6+10;const int mod=998244353,inf=LONG_LONG_MAX;int n,m;int a[N];int ans1[N];int ans2[N];void solve(){cin >> n;for (int i = 1; i <= n; i++ ) cin >> a[i];map<int, int> mp, st;for (int i = 1; i <= n; i++ ) {mp[a[i]]++ ;if(mp[a[i]] > 2){cout<<"NO"<<'\n';return ;}}int cur = 0;vector<int> v;for (int i = 1; i <= n; i++ ) {cur += mp[i];if(!mp[i]) v.push_back(i);if(cur > i){cout<<"NO"<<'\n';return;}}cout << "YES" << endl;for (int i = 1; i <= n; i++ ) {if(mp[a[i]] == 1) {ans1[i] = a[i];ans2[i] = a[i];continue;}if(!st[a[i]]) {auto it = lower_bound(v.begin(), v.end(), a[i]);if(it == v.begin()) {                 //没有小的cout<<"NO"<<'\n';return ;}it-- ;ans1[i] = *it;st[a[i]] = ans1[i];ans2[i] = a[i];v.erase(it);                      //还要删除防止重复} else {ans1[i] = a[i];ans2[i] = st[a[i]];}}for (int i = 1; i <= n; i++ )cout << ans1[i] << " \n"[i == n];for (int i = 1; i <= n; i++ )cout << ans2[i] << " \n"[i == n];}signed main(){int t=1;cin>>t;while(t--) solve();return 0;}