2020杭电多校（第八场）

比赛链接

1003 Clockwise or Counterclockwise

签到。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

struct Point{
	LL x, y;
}p[10];

int main(){
	int T; for(read(T); T; T--){
		read(p[1].x, p[1].y, p[2].x, p[2].y, p[3].x, p[3].y);
		p[1].x = p[2].x - p[1].x, p[1].y = p[2].y - p[1].y;
		p[2].x = p[3].x - p[2].x, p[2].y = p[3].y - p[2].y;
		if(p[1].x * p[2].y - p[1].y * p[2].x > 0)
			puts("Counterclockwise");
		else	puts("Clockwise");
	}
	return 0;
}

---

1006 Fluctuation Limit

第 $i$ 个范围浮动 $k$ 之后与第 $i+1$ 个范围取交得到第 $i+1$ 的新范围，如此更新直到第 $n$ 个，若该过程中出现空集则无法构造。构造这个序列只需从后往前任取合法范围内一个值即可。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int T, n;
LL k, l[N], r[N];

int main(){
	for(read(T); T; T--){
		read(n, k);
		for(int i = 1; i <= n; i++)	read(l[i], r[i]);
		LL nowl = l[1], nowr = r[1];
		bool ok = true;
		for(int i = 2; i <= n; i++){
			nowl -= k, nowr += k;
			nowl = max(nowl, l[i]), nowr = min(nowr, r[i]);
			if(nowl > nowr){ ok = false; break; }
			l[i] = nowl, r[i] = nowr;
		}
		if(!ok)	puts("NO");
		else{
			puts("YES");
			vector<LL> ans(n+5);
			for(int i = n; i >= 1; i--){
				ans[i] = l[i];
				if(i == 1)	break;
				nowl = ans[i] - k, nowr = ans[i] + k;
				l[i-1] = max(l[i-1], nowl), r[i-1] = min(r[i-1], nowr);
				if(l[i-1] > r[i-1])	puts("Something wrong");
			}
			for(int i = 1; i <= n; i++)	printf("%lld%c", ans[i], " \n"[i==n]);
		}
	}
	return 0;
}

---

1008 Hexagon

就找规律……偶数在每一个格子都能拐，奇数有一个没法拐。偶数就以 $R=2$ 为中心，向四周两排两排地扩；奇数就以 $R=3$ 为中心，向四周两排两排地扩。

---

1009 Isomorphic Strings

枚举因数 $k$，暴力把所有循环同构字串哈希出来，暴力判断。

这时限卡的，啧啧啧。。。（比赛的时候队友用 pdbs 里面的 hash_table 代替 map 卡过去的，奇怪的知识增加了～）

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 5000005;
const int MOD[3] = {10000019, 5000011, 7000061};

int power[3][N], base = 233; // hash value of string s[1...i] is stored in h[i]
int h[3][N];
inline int getSubstring(int l, int r, int _){ // get hash value of s[l...r]
	if(l > r)	return 0;
	int res = (h[_][r] - 1ll * h[_][l-1] * power[_][r - l + 1] % MOD[_]) % MOD[_];
	res %= MOD[_]; if(res < 0) res += MOD[_];
	return res;
}

int T, n;
char s[N], t[N];
int b[10000100], id;

inline bool check(int _, int k){
	id++;
	for(int i = 1; i <= k; i++){
		int tmp = (1ll * getSubstring(i, k, _) * power[_][i-1] % MOD[_] + getSubstring(1, i-1, _)) % MOD[_];
		tmp %= MOD[_]; if(tmp < 0)	tmp += MOD[_];
		b[tmp] = id;
	}
	for(int i = 1; i <= n; i += k)
		if(b[getSubstring(i, i + k - 1, _)] != id)	return false;
	return true;
}

void solve(){
	read(n);
	scanf("%s", s+1);
	for(int _ = 0; _ <= 2; _++)
		for(int i = 1; i <= n; i++)
			h[_][i] = (1ll * h[_][i-1] * base % MOD[_] + s[i]) % MOD[_];
	for(int i = 1; i < n; i++){
		if(n % i)	continue;
		bool tag = true;
		for(int _ = 0; _ <= 2; _++){
			if(!check(_, i)){ tag = false; break; }
		}
		if(tag)	return puts("Yes"), void();
	}
	puts("No");
}

int main(){
	for(int _ = 0; _ <= 2; _++){
		power[_][0] = 1;
		for(int i = 1; i <= 5000000; i++)
			power[_][i] = (1ll * power[_][i-1] * base) % MOD[_];
	}
	for(read(T); T; T--)	solve();
	return 0;
}