CF Round #630
A.模拟
给定一个初位置，现在要分别走上走下走右走左各多少步，再给定一个范围
问能否走成而不超界
大减小，判断下越界即可
最好加上一个特判：左走k，右走k，但是范围有且仅有一个值的情况
B.数学
给定n个合数(1-1000)
你现在至多使用m种颜色对他们染色(m<=11)
使得同种颜色中的任意两个元素他们gcd不为1
输出m，和染色方案
其实这题范围是突破口，理解了范围的内含问题就出来了
n个数是合数，那么你开2,3,5,7,11,13,17,19,23,29,31这11个桶把数往里面丢即可
值得注意染色还要是m种，m个中全都要用，所以还要遍历桶内是否有存元素，遍历映射一个颜色值即可
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define INF 1e10+5
#define maxn 10005
#define minn -105
#define ll long long int
#define ull unsigned long long int
#define uint unsigned int
#define re register
inline int read()
{
re int t=0;
re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')
{
t=(t<<3)+(t<<1)+v-48;
v=getchar();
}
return t;
}
bool ok[11];
int pr[11]={2,3,5,7,11,13,17,19,23,29,31};
int a[maxn];
int color[11];
void solve()
{
int n;
int m=0;
memset(ok,0,sizeof(ok));
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
for(int j=0;j<11;j++)
{
if(a[i]%pr[j]==0)
{
a[i]=j;
ok[j]=1;
break;
}
}
}
int cnt=1;
for(int j=0;j<11;j++)
{
if(ok[j])
{
color[j]=cnt;
m++;
cnt++;
}
}
cout<<m<<endl;
for(int i=0;i<n;i++)
{
cout<<color[a[i]]<<" ";
}
cout<<endl;
}
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
solve();
}
return 0;
}
C.数学
给定字符串s，和k，保证k|s，现在问你至少要改多少个字符使得s满足k-complete
思路：其实这题想清楚不难发现，
因为a[jk+i]==a[jk+k-i-1]==a[(j+1)*k+i]
所以所构的字符串无非是一个长为k的回文串，copy了原长/k次而已
现在就是让他的值最小
无非就是统计一下所有长度为k的段中第i号与第k-i-1号字母出现的个数即可
注意遍历方式，第一次遍历i，第二次遍历第j个长为k的段
注意要特判k为奇数的情况
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define INF 1e10+5
#define maxn 200005
#define minn -105
#define ll long long int
#define ull unsigned long long int
#define uint unsigned int
#define re register
inline int read()
{
re int t=0;
re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')
{
t=(t<<3)+(t<<1)+v-48;
v=getchar();
}
return t;
}
char a[maxn<<1];
int cur[34];
void solve()
{
int len,k;
cin>>len>>k;
int ans=len;
for(int i=0;i<len;i++)
{
cin>>a[i];
}
for(int i=0;i<k/2;i++)
{
memset(cur,0,sizeof(cur));
int curmax=0;
for(int j=0;j<len/k;j++)
{
cur[a[j*k+i]-'a']++;
cur[a[j*k+k-i-1]-'a']++;
curmax=max(curmax, cur[a[j*k+i]-'a']);
curmax=max(curmax, cur[a[j*k+k-i-1]-'a']);
}
ans-=curmax;
}
if(k&1)
{
memset(cur,0,sizeof(cur));
int curmax=0;
for(int j=0;j<len/k;j++)
{
cur[a[j*k+k/2]-'a']++;
curmax=max(curmax, cur[a[j*k+k/2]-'a']);
}
ans-=curmax;
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
solve();
}
return 0;
}
D.构造
题意是给定一个k，让你构造一个矩阵
从左上角到右下角寻找到一条路径，使得路径上所有数的位和&最大
有人写了个dp算法求解出来答案为u，真实解为u+k
思路:dp的核心就是贪心，它每一步决策是最优最大的。为了使dp出来的值要小于真实答案，其实我们只要让dp因小失大即可
在最后一步时，opt[n-1][m]=0 opt[n][m-1]=x matrix[n][m] =k（x>>k,x&k=0）
这样就因小失大了，接下来只要保证opt[n][m-1]的取值即可
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define INF 1e10+5
#define maxn 105
#define minn -105
#define ll long long int
#define ull unsigned long long int
#define uint unsigned int
#define re register
inline int read()
{
re int t=0;
re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')
{
t=(t<<3)+(t<<1)+v-48;
v=getchar();
}
return t;
}
int main()
{
ll k;
cin>>k;
ll a=1<<17;
cout<<2<<" "<<3<<endl;
cout<<k+a<<" "<<k<<" 0"<<endl;
cout<<a<<" "<<k+a<<" "<<k<<endl;
return 0;
}