Difference Array - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题是道模拟题,因为不知道有什么好的算法...算是CF特色题吧,guessforces
主要是判断 0 的问题:
因为有了 0 类似 [ 0,x ] 的差分能够构造出 [x];
其他大于0的开两个动态数组 a,b 就硬模拟就行了,模拟完之后就排序
不过要注意老问题: a.size()-1 这个问题
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back //vector函数 #define popb pop_back //vector函数 #define fi first #define se second //const int N=; //const int M=; //const int inf=0x3f3f3f3f; //一般为int赋最大值,不用于memset中 //const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中 int T,n; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); T=read(); while(T--) { n=read(); vector<int> a,b; int num0=0; for(int i=1;i<=n;i++) { int t=read(); if(t) a.pb(t); else num0++; } while(1) { if(num0&&a.size()) b.pb(a[0]),num0--; int len=a.size()-1; //老问题了 for(int i=0;i<len;i++) { if(a[i+1]-a[i]) b.pb(a[i+1]-a[i]); else num0++; } if(b.size()) sort(b.begin(),b.end()); if(b.size()<=1) { if(b.size()==1) printf("%d\n",b[0]); else puts("0"); break; } a=b;b.clear(); } } return 0; }
标签:ch,const,int,ll,memset,CF1707B,define From: https://www.cnblogs.com/Willette/p/17084276.html