长春企业免费建站,洛阳网站建设启辰网络,网页设计与制作实训室厂家,建设宠物店网站A - Avoiding Zero
不难发现如果数组所有元素和为0一定不能满足条件#xff0c;否则一定能满足。 假设所有元素和不为0尝试以下构造#xff0c;如果正数和小于负数和的绝对值#xff0c;那么逆序排列#xff0c;否则顺序排列#xff0c;这样一定满足题意。
#define IO i…A - Avoiding Zero
不难发现如果数组所有元素和为0一定不能满足条件否则一定能满足。 假设所有元素和不为0尝试以下构造如果正数和小于负数和的绝对值那么逆序排列否则顺序排列这样一定满足题意。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includequeue
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N60;
int a[N];
int main()
{IO;int T1;cinT;while(T--){int n;cinn;int s0;int s10,s20;for(int i1;in;i){cina[i];if(a[i]0) s1a[i];else s2a[i];sa[i];}if(s0){coutNO\n;continue;}sort(a1,a1n);if(-s1s2) reverse(a1,a1n); coutYES\n;for(int i1;in;i) couta[i] ;cout\n;}return 0;}B - Chess Cheater
瞎搞的
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includequeue
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N100010;
char s[N];
int n,k;
int main()
{IO;int T1;cinT;while(T--){cinnk;cins1;priority_queueint,vectorint,greaterint q1,q2,q3;priority_queueint p1,p2;int cnt0;for(int i1;in;i){if(s[i]L) cnt;else {if(!cnt) continue;if(icnt1s[i-cnt-1]Wins[i]W) q1.push(cnt);else if(icnt1s[i-cnt-1]W||ins[i]W) q2.push(cnt);else q3.push(cnt);cnt0;}}if(cnt) {if(ncnts[n-cnt]W) q2.push(cnt);else q3.push(cnt);}int res0;while(kq1.size()){auto vq1.top();q1.pop();if(kv) res2*v1,k-v;else p1.push(v);}while(kq2.size()){auto vq2.top();q2.pop();if(kv) res2*v,k-v;else p2.push(v);}while(k(p1.size()||p2.size())){res2*k;k0;}if(kq3.size()) {auto vq3.top();res2*min(k,v)-1;}for(int i1;in;i){if(s[i]W){if(i1s[i-1]W) res2;else res;}}coutres\n;}return 0;
}C - The Hard Work of Paparazzi
刚开始以为是个图论题但是有一个条件就是就算你先到了一个点你仍然要等到那个人出现的时间也就是每个点的时间是确定的因此每个点的时间是确定的考虑dp 状态表示fif_ifi表示目前在第iii个点时答案的最大值 状态转移fimax(fi,fi1)(∣xi−xj∣∣yi−yj∣≤ti−tj)f_imax(f_i,f_i1)(|x_i-x_j||y_i-y_j|\leq t_i-t_j)fimax(fi,fi1)(∣xi−xj∣∣yi−yj∣≤ti−tj)
这样转移会发现复杂度爆炸O(n2)O(n^2)O(n2)我们可以发现还有个东西一直没有用也就是地图的尺寸rrr由于tit_iti是顺序给出的如果当前的ti−tj≥2rt_i-t_j\ge 2rti−tj≥2r不难发现1−j1-j1−j的f1−jf_{1-j}f1−j都能更新fif_ifi由此尝试维护前缀进行优化。 时间复杂度好像是O(nr)O(nr)O(nr)
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includequeue
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N100010;
int r,n;
int f[N];
struct node
{int x,y,t;
}a[N];
int mx[N];
int main()
{IO;int T1;//cinT;while(T--){cinrn;for(int i1;in;i) cina[i].ta[i].xa[i].y;memset(f,-0x3f,sizeof f);memset(mx,-0x3f,sizeof mx);a[0]{1,1,0};f[0]mx[0]0;for(int i1;in;i){for(int ji-1;j0;j--){if(a[i].t-a[j].t2*r) {f[i]max(f[i],mx[j]1);break;}if(abs(a[i].x-a[j].x)abs(a[i].y-a[j].y)a[i].t-a[j].t) f[i]max(f[i],f[j]1);}mx[i]max(mx[i-1],f[i]);}int res0;for(int i1;in;i) resmax(res,f[i]);coutres\n;}return 0;
}剩下的题待补
D - Unshuffling a Deck
今天早上起来想了一下这个题想了个贪心的做法然后上课前交代码发现贪心思路不行然后吃完午饭又想了个做法水过去了
尝试每次使得一个数排列归位。这里尝试按照n−1n−2…1n-1\ n-2\dots \ 1%n−1 n−2… 1的顺序 首先我们让排好序的排成目前已经有cnt个数“归位”这样子{[n,n−1,n−2,...,n−cnt1][...n−cnt][....]}\{[n,n-1,n-2,...,n-cnt1][...n-cnt][....]\}{[n,n−1,n−2,...,n−cnt1][...n−cnt][....]}我们只需要这样划分就可以在此归位一个数 {[1]...[1][1]⏟cnt[len1][len2]}\{ \underbrace{[1]...[1][1]}_{cnt}[len_1][len_2]\}{cnt[1]...[1][1][len1][len2]} 这样操作后原序列即变成{[......][n−cnt,n−cnt1,...,n]}\{[......][n-cnt,n-cnt1,...,n]\}{[......][n−cnt,n−cnt1,...,n]} 然后如法炮制的操作一共进行n次即可归位。还有些细节可以看代码
细节1n奇偶性最后一次操不能让序列变成全部逆序的情况需要顺序 细节2划分需要至少划分2个断最后需要把划分成1个段无效操作清除掉。
上述方法一定能在n次操作以内完成序列顺序。 #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includequeue
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N60;
int n,cnt;
int a[N],b[N];
vectorint ans[N];
int main()
{IO;int T1;//cinT;while(T--){cinn;for(int i1;in;i) cina[i];bool flag;int nown;if(n1) flag0;else flag1;for(int k1;kn;k){int p;for(int i1;in;i) if(a[i]now) pi;//coutp:;//cout(int)flag\n;if(!flag)// 左边整齐{for(int i1;icnt;i) ans[k].push_back(1);if(p-cnt) ans[k].push_back(p-cnt);if(n-p) ans[k].push_back(n-p);for(int ip1,j1;in;i,j) b[j]a[i];// p1~n - 1~n-p n-pfor(int icnt1,jn-p1;ip;i,j) b[j]a[i];// cnt1~p - n-p1 p-cntfor(int i1,jn;icnt;i,j--) b[j]a[i];// 1~cnt - n~n-cnt1 cntfor(int i1;in;i) a[i]b[i];}else{if(p-10) ans[k].push_back(p-1);if(n-cnt-p10) ans[k].push_back(n-cnt-p1);for(int i1;icnt;i) ans[k].push_back(1);for(int i1,jn-p2;ip-1;i,j) b[j]a[i];for(int ip,jcnt1;in-cnt;i,j) b[j]a[i];for(int in-cnt1,jcnt;in;i,j--) b[j]a[i];for(int i1;in;i) a[i]b[i];}now--;cnt;flag^1;}int res0;for(int i1;in;i)if(ans[i].size()1) res;coutres\n;for(int i1;in;i){if(ans[i].size()1){coutans[i].size() ;for(auto t:ans[i]) coutt ;cout\n;}}}return 0;
}E - Xum
要加哟哦~
