网站排名搜索,摄影设计工作室,wordpress下单邮件通知的实现,怎么建设咨询网站题目 思路来源
官方题解
洛谷题解
题解
可操作的最短区间长度肯定是gcd#xff0c;记为g#xff0c;然后考虑如何dp
考虑g个等价类#xff0c;每个等价类i,ig,i2*g,...
每次翻转长度为g的区间#xff0c;会同时影响到g个等价类总的翻转的奇偶性#xff0c;
性质一记为g然后考虑如何dp
考虑g个等价类每个等价类i,ig,i2*g,...
每次翻转长度为g的区间会同时影响到g个等价类总的翻转的奇偶性
性质一只有每个等价类翻的次数奇偶性相同才合法 性质二此外翻1-g和翻2-g1可以起到翻(1,g1)效果
等价类内翻两个相邻的可以类似地叠加成两个不相邻的推广为(i,ix*g) 即等价类内如果有偶数个负数可以两两翻完奇数个负数可以剩一个
此外可以一开始翻一次[1,g]改变每个等价类内负数个数的奇偶性所以两种情况都考虑
也就是考虑将所有数都翻成正数
然后按是否操作一次[1,g]决定在等价类内负数个数为奇/偶时将绝对值最小的数回退掉减掉2倍mn
这就是性质解法 而dp做法则是注意到性质一后dp即可dp[i][j]表示i的等价类的数总共被翻了奇/偶次
枚举当前数翻还是不翻翻的话加1次翻算-a[i]否则加0次翻算a[i]
对每个等价类内dp值求和取翻奇/偶次二者的max
代码1性质
// Problem: D. Flipping Range
// Contest: Codeforces - Codeforces Round 768 (Div. 1)
// URL: https://codeforces.com/contest/1630/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define scll(a) scanf(%lld,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N1e610;
int t,n,m,g,v,a[N];
ll dp[N][2];
//考虑等价类 当前等价类内被翻了奇/偶次 只有每个等价类翻的次数奇偶性相同才合法
//翻1-k和翻2-k1可以起到翻(1,k1)效果 类似地 可以翻(i,ix*k)
void sol(){sci(n),sci(m); ll all0;rep(i,0,n-1){sci(a[i]);allabs(a[i]);}int g0;rep(i,1,m){sci(v);g__gcd(g,v);}ll sum10,sum20;rep(i,0,g-1){int mn2e9,cnt0;for(int ji;jn;jg){mnmin(mn,abs(a[j]));cnt(a[j]0);}if(cnt1)sum1mn;else sum2mn;}printf(%lld\n,all-2ll*min(sum1,sum2));
}
int main(){sci(t); // t1while(t--){sol();}return 0;
}
代码2dp
// Problem: D. Flipping Range
// Contest: Codeforces - Codeforces Round 768 (Div. 1)
// URL: https://codeforces.com/contest/1630/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define scll(a) scanf(%lld,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N1e610;
int t,n,m,g,v,a[N];
ll dp[N][2];
//考虑等价类 当前等价类内被翻了奇/偶次 只有每个等价类翻的次数奇偶性相同才合法
//翻1-k和翻2-k1可以起到翻(1,k1)效果 类似地 可以翻(i,ix*k)
void sol(){sci(n),sci(m); rep(i,0,n-1){sci(a[i]);}int g0;rep(i,1,m){sci(v);g__gcd(g,v);}ll sum10,sum20;rep(i,0,g-1){dp[i][0]0;dp[i][1]-2e9;for(int ji;jn;jg){ll x1dp[i][0],x2dp[i][1];dp[i][0]max(x1a[j],x2-a[j]);dp[i][1]max(x1-a[j],x2a[j]);}sum1dp[i][0];sum2dp[i][1];}printf(%lld\n,max(sum1,sum2));
}
int main(){sci(t); // t1while(t--){sol();}return 0;
}
