Codeforces Round #632 (Div. 2)
CF1333A Little Artem
知识点：
构造
题意：
多次询问一个(n imes m)的网格，每个格子填(0,1)，要求有(0)相邻的(1)的个数是有(1)相邻的(0)的个数(+1)，求一种方案。
解法：
因为(n)和(m)都不小于(2)，所以直接构造第一行第一列是(0)，其他是(1)即可。
备注：
无
#include<bits/stdc++.h>
using namespace std;
int T,n,m;
int main()
{
int i,j;
cin>>T;
while (T--)
{
cin>>n>>m;
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
if (i==1&&j==1)
putchar('W');
else
putchar('B');
}
puts("");
}
}
}
CF1333B Kind Anton
知识点：
模拟
题意：
给定两个序列，第一个序列的数是({-1,0,1})中的数。一个序列可以操作无限次，每次操作选定不同的两个数((i,j))，要求(ileq j , a_j=a_i+a_j)，问第一个序列是否能变成第二个，多次询问。
解法：
因为后面的数不会对前面产生贡献，所以从后往前模拟一遍，用两个计数器分别记录当前点前面的(-1,1)的个数，然后看差值的正负判断即可。
备注：
无
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int T,n,a[maxn],b[maxn],c[5],ans;
int main()
{
int i;
cin>>T;
while (T--)
{
cin>>n;
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
cin>>a[i];
c[a[i]+1]++;
}
for (i=1;i<=n;i++)
cin>>b[i];
ans=1;
for (i=n;i>=1;i--)
{
c[a[i]+1]--;
if (a[i]==b[i])
continue;
int d=b[i]-a[i];
if (d>0)
{
if (c[2]<=0)
{
ans=0;
break;
}
}
if (d<0)
{
if (c[0]<=0)
{
ans=0;
break;
}
}
}
puts(ans?"YES":"NO");
}
}
CF1333C Eugene and an array
知识点：
计数，前缀和，双指针
题意：
给定一个序列，定义一个序列是好的为这个序列的所有非空子串都不为(0)。问一个序列的所有子串中是好的有多少个。
解法：
经过多次尝试（本来我想用一种在(ABC)中见过的方法，就是统计不合法的有多少个，但是发现这样去不了重，所以不行），发现肯定是
先求前缀和，假如一个子串是好的，那一定是这个子串中不会出现前缀和相等的数而且当前右端点的(a_i)不为(0)。发现这个东西是有单调性的，所以用(map)维护每个前缀和出现的次数，然后两个指针维护当前的合法区间，是线性的。
备注：
这道题我还(WA)了两次，要特别注意当前点的(a_i)为(0)的情况，这种情况直接特判不算进答案里。但是右移指针的方法没变，还是找到第一个令当前前缀和次数为(1)为止。因为这个区间是前缀和区间，假如(l=r)那么就没有东西了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200010;
int n,a[maxn];
ll ans,s[maxn];
map<ll,int>mp;
#define mkp make_pair
int main()
{
int i,l,r;
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
if (n==1)
{
if (a[1]==0)
puts("0");
else
puts("1");
return 0;
}
l=0;
mp.insert(mkp(0,1));
for (r=1;r<=n;r++)
{
if (mp.find(s[r])==mp.end())
mp.insert(mkp(s[r],1));
else
mp[s[r]]++;
/*if (a[r]==0)
{
while (l<=r)
{
mp[s[l]]--;
l++;
}
continue;
}*/
while (mp[s[r]]==2&&l<=r)
{
mp[s[l]]--;
l++;
}
if (a[r]!=0)
ans+=r-l;
}
printf("%lld
",ans);
return 0;
}
CF1333D Challenges in school №41
知识点：
贪心，逆序对，冒泡排序
题意：
有一个序列，每个位置要么往左看要么往右看，现在每一秒可以让至少一对盯着对方的人同时转头，但是同一秒一个人只能转一次。问恰
好(k)步使得没有人互相盯着的一种方案。
解法：
显然，在最后肯定是左边一段的人全都看着左边，右边剩下的人都看着右边才能满足条件。于是我们让(L)为(0)，(R)为(1)。我们进行一轮冒泡排序，可以让若干对盯着对方的人（也就是逆序对）交换，而且可以发现这些人肯定是不会重复的，而且是这轮中能选的最多的了。然后交换，冒泡直到没有逆序对为止。那么答案的下界就是冒泡的次数，上界就是冒泡影响过的位置的总次数（每一次交换我们都拆开来算一次）。假如答案不在这个区间内，那就无解。否则肯定有解。然后用调整法，让前面若干轮直接冒泡，后面的拆开来一次次地冒泡即可。
备注：
可以先求一个冒泡的前缀和，方便后面统计，而且这道题细节很繁琐。
#include<bits/stdc++.h>
using namespace std;
const int maxn=3010;
int n,k,a[maxn],s[maxn],minv,maxv;
vector<int>v[maxn];
char c[maxn];
#define pb push_back
int main()
{
int i,j,cnt,cur;
scanf("%d%d%s",&n,&k,c+1);
for (i=1;i<=n;i++)
a[i]=(c[i]=='R');
for (i=1;i<=n;i++)
{
cnt=0;
for (j=1;j<n;j++)
if (a[j]>a[j+1])
{
++cnt;
v[i].pb(j);
}
maxv+=cnt;
s[i]=maxv;
if (!cnt)
{
minv=i-1;
break;
}
for (j=0;j<cnt;j++)
swap(a[v[i][j]],a[v[i][j]+1]);
}
if (k<minv||k>maxv)
{
puts("-1");
return 0;
}
if (k==minv)
{
for (i=1;i<=minv;i++)
{
cnt=v[i].size();
printf("%d ",cnt);
for (j=0;j<cnt;j++)
printf("%d ",v[i][j]);
puts("");
}
return 0;
}
cur=0;
while (cur<minv&&maxv-s[cur+1]+cur+1>=k)
cur++;
for (i=1;i<=cur;i++)
{
cnt=v[i].size();
printf("%d ",cnt);
for (j=0;j<cnt;j++)
printf("%d ",v[i][j]);
puts("");
}
if (maxv-s[cur]+cur-k+1>0)
{
cnt=maxv-s[cur]+cur-k+1;
printf("%d ",cnt);
for (j=0;j<cnt;j++)
printf("%d ",v[cur+1][j]);
puts("");
}
cnt=v[cur+1].size();
for (j=maxv-s[cur]+cur-k+1;j<cnt;j++)
printf("1 %d
",v[cur+1][j]);
for (i=cur+2;i<=minv;i++)
{
cnt=v[i].size();
for (j=0;j<cnt;j++)
printf("1 %d
",v[i][j]);
}
return 0;
}
CF1333E Road to 1600
知识点：
构造
题意：
解法：
不会
备注：
CF1333F Kate and imperfection
知识点：
数学，(GCD)，线性筛
题意：
给定一个(n)，一个集合里有不超过(n)的所有正整数。要求对于每一个(2)到(n)的(k)，所有大小为(k)的集合中，对于每个集合，两两求出(GCD)，每个集合的贡献是最大的(GCD)，而对于每个(k)的答案是当前所有集合中的贡献值的最小值。求出所有的贡献最小值。
解法：
首先可以观察到一个性质，假如一个数(x)要加入当前某个集合，那么它所有的真因子都肯定在里面。原因是假如不在的话肯定假如那些
真因子更优。而假如之后这个数产生的贡献(GCD)最大值肯定是(x)的最大真因子。有因为能加入(x)了，答案肯定不会变小，所以答案肯
定就是这个最大真因子。而最大真因子等于(x)除以最小质因子，也就是线性筛中筛到的第一个质数对应的(i)，那么那这个来排个序然
后从小到大加入数就是答案了。
备注：
注意：1，线性筛中的(i)是否是当前质数的倍数这个要放在处理完因数之后。2，质数个数最好开(n)这么大，否则有可能(RE)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=500010;
int n,m,pr[maxn],mc[maxn];
bool v[maxn];
int main()
{
int i,j;
cin>>n;
for (i=2;i<=n;i++)
{
if (!v[i])
{
pr[++m]=i;
mc[i]=1;
}
for (j=1;j<=m&&pr[j]*i<=n;j++)
{
v[pr[j]*i]=1;
mc[pr[j]*i]=i;
if (i%pr[j]==0)
break;
}
}
sort(mc+2,mc+n+1);
for (i=2;i<=n;i++)
printf("%d ",mc[i]);
puts("");
return 0;
}