Codeforces Round #630 (Div. 2) （ABC）

Codeforces Round #630 (Div. 2) （ABC）

A Exercising Walk

水題
題意 就是給你一個起點（x,y），四個數字分別表示左，右，下，上四個方向的移動步數，然后，給你一個范圍(x1 <= x <= x2, y1 <=y <= y2)移動程序中必須滿足，移動順序可以任意，
坑點 –菜雞的自己wa了–
和大多數題的移動方向不一樣，
左移動為x-1
右移動為x+1
下移動為y-1
上移動為y+1

#include <cstdio>
#include <cstring>

int T, le, ri, down, up;
int x, y, x1, y1, x2, y2;

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d%d", &le, &ri, &down, &up);
		scanf("%d%d%d%d%d%d", &x, &y, &x1, &y1, &x2, &y2);
		if(le && ri && le == ri){
			if(x - 1 < x1 && x + 1 > x2){
				printf("No\n");
				continue;
			}
		}
		if(down && up && down == up){
			if(y - 1 < y1 && y + 1 > y2){
				printf("No\n");
				continue;
			}
		}
		x += ri - le;
		y += up - down;
		if(x >= x1 && x <= x2 && y >= y1 && y <= y2){
			printf("Yes\n");
		} else {
			printf("No\n");
		}
	}
	return 0;
} 

B. Composite Coloring

水題

題意感覺主要是題目比較難理解 對英語菜雞的自己來說
大意就是 T 組樣例， 給你 n 個數，然后找他們的質因子，相同的它們就是是一種顏色（輸出的數字相同），不同就換種新顏色（換一個新數字），
不過輸出的數字都必須 大于等于 1，小于等于 11，（題目已經證明顏色個數在11以內，所以從1開始向上加就對了），
思路
先根據資料范圍把可能用到的所有素數給打表，存在 prime 陣列里，
然后遍歷每一個數，在 prime 陣列從左到右找它對應的顏色，顏色用 vis 陣列標記是否用過，若沒用過那就加一個新顏色，否則就用舊顏色（用過的顏色），

#include <cstdio>
#include <cstring>

const int N = 1005;
int T, n;
int a[N];
int prime[N], vis[N], sum;
int ans[N];

bool pd(int x){
    for(int i=2; i*i<=x; i++)
	if(x % i == 0 ) return false;
    return true;
}

int main(){
    for(int i=2; i<=1000; i++){
    	if(pd(i)) prime[++sum] = i;
	}   
	scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int cnt = 0;
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; i++){
            scanf("%d",&a[i]);
            for(int j=1; j<=sum; j++) 
			if(a[i] % prime[j] == 0){
            	if(!vis[j]) {
					vis[j] = ++cnt;
				}
        		ans[i] = vis[j];
				break;
            }
        }
        printf("%d\n",cnt);
        for(int i=1; i<n; i++) 
		printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
    }
    return 0;
}

C. K-Complete Word

思維題
回文規律
1 = n
2 = n - 1
3 = n - 2
4 = n - 3
5 = n - 4

周期規律
n 2
1 = 3 = 5 = n - 1
2 = 4 = 6 = n

n 3
1 = 4 = 7 = n - 2
2 = 5 = 8 = n - 1
3 = 6 = 9 = n

n 4
1 = 5 = 9 = n - 3
2 = 6 = 10 = n - 2
3 = 7 = 11 = n - 1
4 = 8 = 12 = n

根據回文串和 k 周期的規律總和，就可以發現
k周期的規律中第 i 個周期都和第 k - i + 1 個周期元素相同然后把他們融合為一組，每一組找到元素數最大的個數 sum，再用應該完全相同的個數 n / k * 2 減去 sum，就是這組應該變的元素數，（若 i == k - i + 1則表明只有一個周期，所以就它自己為一組就行），

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

const int N = 2e5 + 10;
char s[N];
int T, n, k; 

int main(){
	scanf("%d",&T);
	while(T--){
		map<char,int> mp;
		scanf("%d%d",&n,&k);
		scanf("%s",s+1);
		int ans = 0, sum1 = 0, sum2 = 0;
		for(int i=1; i<=(k+1)>>1; ++i){
			int l = i, r = k - i + 1;
//			printf("%d %d\n",l,r);
			if(l == r){
				mp.clear();
				sum1 = 0;
				for(int j=l; j<=n; j+=k){
					mp[s[j]]++;
					if(mp[s[j]] > sum1){
						sum1 = mp[s[j]];
					}
				}
				ans += n / k - sum1;
			} else {
				sum2 = 0;
				mp.clear();
				for(int j=l; j<=n; j+=k){
					mp[s[j]]++;
					if(mp[s[j]] > sum2){
						sum2 = mp[s[j]];
					}
				}
				for(int j=r; j<=n; j+=k){
					mp[s[j]]++;
					if(mp[s[j]] > sum2){
						sum2 = mp[s[j]];
					}
				}
				ans += n / k * 2 - sum2;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}