好像中文互联网没有相关内容?
题意是给出一个数组能否k等分其子数组,使得k个子段和一样
当时想的有点难了,主要是感觉这算是个经典问题,就上网搜,搜了半天发现lc只有一个用dfs找的
dfs爆搜能行么?肯定不行,这1e7数据是开玩笑的?然后就歪了,当时想的是维护一个滑动窗口然后就暴力摁算,但是其实这个思路一开始就是歪了吧唧的。
这题好久之前的了,今天和朋友聊天突然想到这个题是不是可以用二分试试运气,去试试切一块能够整分的出来,看看能不能让其他的k-1段自然分开,
断还成链这波操作都很熟悉,然后写了两个二分,看看能不能通过二分O(klog(k))在环形的n个地方判断能不能等分,复杂度
其实也不是没想过能不能二分,但是1e7,n和k都是1e7,最坏复杂度O(nklogk),1e15这个估计要算几百年吧?一交wa了,看了下,哦,判断条件放错位置了,然后改了之后结果过了???而且跑得飞快,把直接榜一了。。。。
后来想想这个nklogk好像实际如果能分的话应该不出几次就能分好,应该是可以证明的,有点坑了属于是
代码:
#include <bits/stdc++.h> using namespace std; #define limit (2000000 + 5)//防止溢出 #define INF 0x3f3f3f3f #define inf 0x3f3f3f3f3f #define lowbit(i) i&(-i)//一步两步 #define EPS 1e-9 #define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0); #define ff(a) printf("%d\n",a ); #define pi(a,b) pair<a,b> #define rep(i, a, b) for(ll i = a; i <= b ; ++i) #define per(i, a, b) for(ll i = b ; i >= a ; --i) #define MOD 998244353 #define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next) #define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin) #define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout) #define debug(x) cout<<x<<endl typedef long long ll; typedef unsigned long long ull; char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf; inline ll read(){ #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) ll sign = 1, x = 0;char s = getchar(); while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();} while(s >= '0' && s <= '9'){x = (x << 3) + (x << 1) + s - '0';s = getchar();} return x * sign; #undef getchar }//快读 void print(ll x) { if(x/ 10) print(x / 10); *O++=x % 10+'0'; } void write(ll x, char c = 't') { if(x < 0)putchar('-'),x = -x; print(x); if(!isalpha(c))*O++ = c; fwrite(obuf,O-obuf,1,stdout); O = obuf; } int kase; int n, m,k; int a[limit]; ll sum[limit]; ll target, seg; ll ask(int l, int r){ return sum[r] - sum[l - 1]; } bool check(int x, int st){ int iter = x + 1; rep(i,1, seg - 1){ int l = iter , r = st + n; int flag = 0; while (l <= r){ int mid = l + (r - l) / 2; if(ask(iter, mid) == target){ iter = mid + 1; flag = 1; break; }else if(ask(iter, mid) < target){ l = mid + 1; }else{ r = mid - 1; } } if(!flag){ return false; } } return true; } bool bin_search(int x){ int l = x , r = x + n; while (l <= r){ int mid = l + (r - l) / 2; if(ask(x, mid) < target){ l = mid + 1; }else if(ask(x, mid) > target){ r = mid - 1; }else{ return check(mid, x); } } return false; } void solve(){ cin>>k>>n; rep(i,1,n){ cin>>a[i]; a[i + n] = a[i]; } seg = k; rep(i,1,n<<1){ sum[i] = sum[i - 1] + a[i]; } if(sum[n] % k){ cout<<"NO"<<endl; return; } target = sum[n] / k; rep(i,1,n){ if(bin_search(i)){ cout<<"YES"<<endl; return; } } cout<<"NO"<<endl; } int32_t main() { #ifdef LOCAL FOPEN; // FOUT; #endif FASTIO // cin>>kase; // while (kase--) solve(); cerr << "Time elapsed: " << 1.0*clock()/CLOCKS_PER_SEC << "s\n"; return 0; }