北碚集团网站建设,创建官方网站,网站建设上海网站建设公司网站,英雄联盟网站建设那天晚上和同学打球打的有点晚#xff0c;结果就鸽了#xff0c;现在来补一下
A - Ahahahahahahahaha
直接看原数组中0的个数cnt0和1的个数cnt1#xff0c;谁多留谁即可#xff0c;注意留1的时候要留偶数个。
#define IO ios::sync_with_stdio(false);cin.tie();cout.ti…那天晚上和同学打球打的有点晚结果就鸽了现在来补一下
A - Ahahahahahahahaha
直接看原数组中0的个数cnt0和1的个数cnt1谁多留谁即可注意留1的时候要留偶数个。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N1010;
int a[N];
int n;
int main()
{IO;int T1;cinT;while(T--){cinn;for(int i1;in;i) cina[i];int cnt00,cnt10;for(int i1;in;i){if(a[i]) cnt1;else cnt0;}if(cnt1n/2){coutcnt0\n;for(int i1;icnt0;i) cout0 ;cout\n;}else{if(cnt11) cnt1--;coutcnt1\n;for(int i1;icnt1;i) cout1 ;cout\n;}}return 0;
}B - Big Vova
直接暴力从第一位开始每次选一个目前使c[i]最大的数即可维护d使之为dgcd(b1,b2…bi)dgcd(b_1,b_2\dots b_i)dgcd(b1,b2…bi) 时间复杂度O(n2logn)O(n^2logn)O(n2logn)
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
const int N1010;
int a[N],b[N],n;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
int main()
{IO;int T1;cinT;while(T--){cinn;int d0;for(int i1;in;i){cina[i];dmax(a[i],d);}for(int i1;in;i){int mx0;int p-1;for(int j1;jn;j){if(a[j]0) continue;//之前选过if(mxgcd(d,a[j])){mxgcd(d,a[j]);pj;}}b[i]a[p];dgcd(d,b[i]);a[p]0;}for(int i1;in;i) coutb[i] ;cout\n;}return 0;
}C - Chocolate Bunny
交互题第一次做什么东西啊 每次选择没有确定的两个位置ij询问i、j和j、i。分析可知这样一定能确定一个位置的数。总询问次数为2n−22n-22n−2次即可原序列。 如果aiaja_ia_jaiaj已知ai%ajxa_i \%a_j xai%ajx和aj%aiya_j \%a_i yaj%aiy分析可知a[j]ya[j]ya[j]y即确定了一个位置的数。 如果aiaja_ia_jaiaj已知ai%ajxa_i \%a_j xai%ajx和aj%aiya_j \%a_i yaj%aiy分析可知a[i]xa[i]xa[i]x也能能够确定一个位置的数。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
const int N10010;
int a[N],n;
bool st[N];
int main()
{IO;int T1;//cinT;while(T--){cinn;int x,y,now1;for(int i2;in;i){cout? now i\n;cout.flush();cinx;cout? i now\n;cout.flush();ciny;if(xy){a[now]x;st[x]1;nowi;}else{a[i]y;st[y]1;}}for(int i1;in;i)if(!st[i]) a[now]i;cout! ;for(int i1;in;i) couta[i] ;cout\n;}return 0;
}D - Discrete Centrifugal Jumps
f[i]min(f[i],f[k]1)f[i]min(f[i],f[k]1)f[i]min(f[i],f[k]1) 对于h[k1…i−1]h[k1\dots i-1]h[k1…i−1]满足题目条件即可
// O(n^2)
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
const int N300010;
int h[N],n;
int f[N];
int main()
{IO;int T1;//cinT;while(T--){cinn;for(int i1;in;i) cinh[i];memset(f,0x3f,sizeof f);f[1]0;for(int i1;in;i){int maxh0,minh0x3f3f3f3f;for(int ji-1;j;j--){if(minhmax(h[i],h[j])||maxhmin(h[i],h[j]))f[i]min(f[i],f[j]1);minhmin(minh,h[j]);maxhmax(maxh,h[j]);}}coutf[n]endl;}return 0;
}尝试采用单调栈维护一个单调序列不妨先考虑一种情况即max(hi1,…,hj−1)min(hi,hj)max(h_{i1},…,h_{j−1})min(h_i,h_j)max(hi1,…,hj−1)min(hi,hj)维护严格单调上升的序列对于第iii个山峰考虑合法转移对于单调栈中的元素如果第一个大于hih_ihi中的下标是pospospos那么f[pos−1]…f[tt]f[pos-1]\dots f[tt]f[pos−1]…f[tt]都可以更新f[i]f[i]f[i]在维护有序栈的同时更新不断更新答案即可
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
const int N300010;
int h[N],n;
int q1[N],tt1;
int q2[N],tt2;
int f[N];
int main()
{IO;int T1;//cinT;while(T--){cinn;for(int i1;in;i) cinh[i];q1[tt1]1,q2[tt2]1;for(int i2;in;i){f[i]f[i-1]1;while(tt1h[q1[tt1]]h[i])f[i]min(f[q1[tt1--]]1,f[i]);if(tt1) f[i]min(f[q1[tt1]]1,f[i]);while(tt1h[q1[tt1]]h[i]) tt1--;q1[tt1]i;while(tt2h[q2[tt2]]h[i])f[i]min(f[q2[tt2--]]1,f[i]);if(tt2) f[i]min(f[q2[tt2]]1,f[i]);while(tt2h[q2[tt2]]h[i]) tt2--;q2[tt2]i;}coutf[n]\n;}return 0;
}要加油哦~
