【解题报告】CF DIV2 #ROUND 717 A~D
比赛链接 排名3694，终于上分了，回归pupil好耶
A. Tit for Tat
思路
简单的贪心，字典序最小那就让前面的-1，然后+1全部加到最后一个数上即可
代码
// Problem: A. Tit for Tat
// Contest: Codeforces - Codeforces Round #717 (Div. 2)
// URL: https://codeforces.com/contest/1516/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// FishingRod
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
#define MULINPUT
/*DATA & KEY
t 1 20
n 2 100
k 1 10000
ai 0 100
*/
int T;
const int N=205;
int a[N];
void solve(int C)
{
//NEW DATA CLEAN
memset(a,0,sizeof a);
//NOTE!!!
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
int pos=1;
while(k--)
{
while(a[pos]<=0)pos++;
if(pos>=n)break;
a[pos]--,a[n]++;
}
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
puts("");
}
int main()
{
#ifdef MULINPUT
scanf("%d",&T);
for(int i=1;i<=T;i++)solve(i);
#else
solve(1);
#endif
return 0;
}
B. AGAGA XOOORRR
思路
比较有意思的一题，很多人FST了不清楚为啥，主要思想是异或前缀和。
原本用前后缀写了个假算法，后来找到数据发现假了
方法比较多吧。讲讲大致思路，题目说可以把两个相邻的数替换成他们的异或值，问最后能不能把数组里的值都变成一样的，数组值的数量至少为2
其实嘛，就是把这个数组化成几个块，然后这几个块组内异或成一个值。问有没有办法让他们异或出来的值都相等
我们从最终结果考虑，那么分为两种情况,假设最终的值都为X,任意数量都可以化成三个或者两个块（其实到这里的话你可以暴力枚举分界线，一条分界线和两条分界线）
例如
X ^ X ^ X ^ X=X ^ X
X ^ X ^ X ^ X ^ X= X ^ X ^ X
如果块为奇数，那么X ^ X ^ X =X，也就是全部异或起来为X
然后利用异或前缀和，找到前缀和为X的第一个位置POS1，然后反向找一个前缀和为0的位置POS2，如果POS1 POS2都存在并且POS1<POS2那么就输出YES
如果块为偶数，那么X ^ X =0,也就是全部异或起来为0直接输出YES就完事了
除了以上情况都输出NO
代码
// Problem: B. AGAGA XOOORRR
// Contest: Codeforces - Codeforces Round #717 (Div. 2)
// URL: https://codeforces.com/contest/1516/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// FishingRod
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
#define MULINPUT
/*DATA & KEY
t 1 15
n 2 2000
ai 0 2^30
*/
int T;
const int N=2E3+10;
LL a[N],pre[N];
void solve(int C)
{
//NEW DATA CLEAN
memset(a,0,sizeof a);
memset(pre,0,sizeof pre);
//NOTE!!!
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
pre[1]=a[1];
for(int i=2;i<=n;i++)pre[i]=pre[i-1]^a[i];
if(pre[n]==0){puts("YES");return;}
int pos1,pos2;
bool flag=0;
for(int i=1;i<=n;i++)
if(pre[i]==pre[n])
{pos1=i;break;}
for(int i=n;i>=1;i--)
if(pre[i]==0)
{pos2=i;flag=1;break;}
if(flag&&(pos1<pos2))puts("YES");
else puts("NO");
}
int main()
{
#ifdef MULINPUT
scanf("%d",&T);
for(int i=1;i<=T;i++)solve(i);
#else
solve(1);
#endif
return 0;
}
C. Baby Ehab Partitions Again
思路
题意：定义一个好的数组：将他的元素不重不漏地划分成两个子序列，不存在一种划分方式使得两个子序列的和是相等的。现在给你长度为n的一个数组，你可以删除其中的一些数，来让他成为一个好数组，问最少删除几个
两个子序列下意识会想到01背包选与不选的操作吧。然后这题是利用了奇数偶数的性质，很妙啊。
首先思考一下最简单的情况，如果数组和为奇数，那么一定是好数组。
然后是偶数的，首先01背包看能不能分出来。
如果不能分出来，那么皆大欢喜，不用删除。
如果能分出来，那就要去掉数了，实际上只要去点任意一个数就可以了。数组里有奇数那么直接去掉奇数就可以了，因为剩下和为奇数不可分。如果全是偶数的话，那么对所有元素除2，直到出现奇数，然后删掉这个数就可以了。（为啥可以除2呢？我们已经确定进入这个分支的数组是可以划分成两个和相同的子序列的，那么这个结果对于除2知乎的数组是一样的，那么已知转化到出现奇数即可）实际上，我们可以直接除这个数组的公约数，然后看哪个数是奇数。
代码
// Problem: C. Baby Ehab Partitions Again
// Contest: Codeforces - Codeforces Round #717 (Div. 2)
// URL: https://codeforces.com/contest/1516/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// FishingRod
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
//#define MULINPUT
/*DATA & KEY
n 2 100
ai 1 2000
*/
int T;
const int N=105,M=2e5+10;
LL a[N],f[M];
void solve(int C)
{
//NEW DATA CLEAN
//NOTE!!!
int n,pos;cin>>n;
bool flag=0;
LL sum=0,g=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];g=__gcd(g,a[i]);
if(a[i]&1&&!flag)
{
flag=1;
pos=i;
}
}
if(sum&1)puts("0");
else
{
for(int i=1;i<=n;i++)
for(int j=sum/2;j>=a[i];j--)
f[j]=max(f[j],f[j-a[i]]+a[i]);
if(f[sum/2]==sum/2)
{
puts("1");
if(flag)cout<<pos<<endl;
else
{
for(int i=1;i<=n;i++)
if((a[i]/g)&1)
{
cout<<i<<endl;
break;
}
}
}
else puts("0");
}
}
int main()
{
#ifdef MULINPUT
scanf("%d",&T);
for(int i=1;i<=T;i++)solve(i);
#else
solve(1);
#endif
return 0;
}
D. Cut（待补）
思路
这题只学了思路等我学了倍增DP再来瞅瞅，丢一道牛客例题：区间的连续段
题意给你长度为n的数字，有q次查询。每次查询区间[l,r]，要求对这个区间内的数分块，对于每个分块，他们的LCM=他们的乘积，也就是块内元素互质，gcd=1，问最少分多少块
参考这位大佬的博客（双指针版本+倍增） 主要是倍增思想的优化DP，没接触过的玩意呢
搜了一下资料，可以参考一下这篇超级萌的解说！
①条件转化
如何让组尽可能的少？一个显然的思想是让每组长度尽可能地长，装的元素尽可能多。
那么如何确定最长能扩展到哪里呢？
由区间LCM=元素乘积–>区间元素两两互质–>分解质因数后，待加入a[i]分解出来的数是原来区间没有的
！！！需要注意的是，在第一段推理过程中不能说成，因为区间LCM=元素乘积->区间gcd=1->两两互质（加粗的这段推理是不正确的,区分两两互质和整体互质）
但是这样是可以的区间LCM=元素乘积->两两互质->区间gcd=1
②预处理每个（暴力枚举1~n）起点最远能扩展到的地方
这部分还参考了这篇博客 双指针一个个移动优化为倍增移动
预处理的区间都互质，
与区间内的某个数不互质
倍增优化：
定义为从起点i，跳
次能到的地方
状态转移：
③倍增查询
不是很懂
代码
由于本人实在太弱鸡，只能照抄官方代码加解释了
#include <bits/stdc++.h>
using namespace std;
#define MX 100000
vector<int> p[100005];
int a[100005],nex[100005],dp[20][100005];//nex数组
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=2;i<=MX;i++)//类似埃筛预处理一波
{
if (p[i].empty())
{
nex[i]=n+1;
for (int j=i;j<=MX;j+=i)
p[j].push_back(i);
}
}
dp[0][n+1]=n+1;//起点n+1，跳2^0次能到的地方
for (int i=n;i>0;i--)
{
dp[0][i]=dp[0][i+1];
for (int j:p[a[i]])
{
dp[0][i]=min(dp[0][i],nex[j]);
nex[j]=i;
}
}
//预处理部分
for (int i=1;i<20;i++)
{
for (int j=1;j<=n+1;j++)
dp[i][j]=dp[i-1][dp[i-1][j]];
}
//查询部分
while (q--)
{
int l,r,ans=0;
scanf("%d%d",&l,&r);
for (int i=19;i>=0;i--)//这部分看由几个完整的区间
{
if (dp[i][l]<=r)
{
ans+=(1<<i);
l=dp[i][l];
}
}
printf("%d\n",ans+1);
}
}
反思
A：
手速贪心即可
B:
从最终结果形式反推思考
分块思想，思考每一块要满足的性质，分块问题有时候我们暴力枚举分割线
异或前缀和，要运用好x^x=0,x ^ 0=x这两个来推断区间值
值相同的时候，几个异或结果可以合并
C:
两组可以联想到01背包。
如果两个数相同，他们的和一定为偶数
这题引出奇偶性的切入点是最开始最简单的情况，整体和为奇数。
D:
区间LCM=元素乘积->两两互质->区间gcd=1
如何让组尽可能的少？一个显然的思想是让每组长度尽可能地长，装的元素尽可能多。
找最长满足条件的区间：双指针，双指针移动可以用倍增优化
补一个博客（D题里由链接）里看到的双指针伪代码模板
int L=1,R=1;
while(R<=n)
{
add(a[R]);
while(当前状态不符合)
{
delete(a[L]);
L++;
}
记录(a[L]~a[R])对应答案;
R++;
}