2020 Multi-University Training Contest 8

8.13 愉快且排名新高的杭电8

1002-Breaking Down News

题意

给定长度为 $n$ 的数组 $a$ ,对于任意 $i$ 都有 $-1\leq a_i\leq 1$ 。想要将 $a$ 划分做若干块使得每块总和的 $sgn$ 和最大,每块的长度需要满足 $l\leq len\leq r$ 。

思路

由于 $dp_i$ 只能从 $dp_{i-r}-dp_{i-l}$ 转移过来,所以记录前缀和每次求区间最值。参考别人代码用 $multiset$ 和 $lowerbound$ ,怪好看的233

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
typedef pair<int,int> pii;
const int maxn = 1e6 + 5;
int a[maxn],q[maxn];
multiset<pii>s;
int sgn(int x){ return x<0?-1:(x>0); }
int solve(){
int n,l,r; sc(n); sc(l); sc(r); s.clear();
rep(i,1,n+1) sc(a[i]),a[i]+=a[i-1];
rep(i,1,l) q[i]=-n; rep(i,l,n+1){
s.insert({q[i-l],-a[i-l]});
pii t=*--s.end();
q[i]=t.first+sgn(a[i]+t.second);
multiset<pii>::iterator it;
it=s.lower_bound({t.first,-n});
if(it!=s.begin()){
t=*--it;
q[i]=max(q[i],t.first+sgn(a[i]+t.second));
} if(r<=i) s.erase(s.find({q[i-r],-a[i-r]}));
} return pf("%d\n",q[n]);
}
int main(){
int _; sc(_); while(_--) solve();
}

1003-Clockwise or Counterclockwise

题意

给定在以原点为圆心的圆上三个点。问这三个点是顺时针还是逆时针。

思路

套了个求多边形面积的板子,判面积正负就过了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
typedef long long ll;
struct point{ ll x,y; }p[5];
__int128 parea(point p[],int n){
if(n<3) return 0;
__int128 ans=0; p[n]=p[0];
rep(i,0,n) ans+=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
return ans/2;
}
int solve(){
rep(i,0,3) scl(p[i].x),scl(p[i].y);
__int128 s=parea(p,3);
return puts(s<0?"Clockwise":"Counterclockwise");
}
int main(){
int _; sc(_); while(_--) solve();
}

1006-Fluctuation Limit

题意

给定 $n$ 段限制,问能否找到可以满足每段限制的方案,方案之间差值最大为 $k$ 。

思路

因为不会 $dp$ 直接考虑贪心(确实不是 $dp$ )。求出每段满足题意的 $l$ 、$r$ ,最后倒推回去。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
ll a[maxn],b[maxn],c[maxn],l[maxn],r[maxn];
int solve(){
int n,ff(0); ll k; sc(n); scl(k);
l[0]=-1e18,r[0]=1e18; rep(i,1,n+1){
scl(a[i]),scl(b[i]);
l[i]=max(a[i],l[i-1]-k);
r[i]=min(b[i],r[i-1]+k);
if(l[i]>r[i]) ff++;
} if(ff) return pf("NO\n"); pf("YES\n");
c[n]=l[n]; ll lt=l[n],rt=l[n];
dep(i,n-1,1){
lt=max(lt-k,l[i]);
rt=min(rt+k,r[i]);
c[i]=lt+rt>>1;
} rep(i,1,n+1) pf("%lld%c",c[i]," \n"[i==n]);
return 0;
}
int main(){
int _; sc(_); while(_--) solve();
}

1008-Hexacppn

题意

给定半径为 $n$ 的六边形网格图,可以任意选择起点,问不重复地走满全部网格且转弯最多的路径方案。

思路

团体智慧的聚集,小转画图,小庄造数据,小潘找规律写代码

分奇数和偶数进行分析

偶数时,直接从左上角开始从外到内的绕圈,最后会正好绕完

奇数时,可以视为前一个半径 $(r - 2)$ 的图外面再多绕一圈,绕法与偶数相同

写的时候就先把半径为 $3$ 和 $4$ 的结果写好,完事拿着前一个绕就行了,节省时间可以打个不同位置的表来绕

嗯,花花大法好

奇数情况:

 

1009-Isomorphic Strings

题意

给定串 $s$ ,问能否均等地划分成 $k$ 份,使得每份互为循环同构。

思路

备注:理论复杂度不低,但是很难卡满,$O(能过)$ ,甚至没到 $1s$

枚举每个因数,对每个因数 $check$ 。

求出第一块的哈希值,之后每块和第一块的对比。如果和第一块不同就枚举循环同构,递推求循环同构的哈希值,具体是 $(hash-a[pos_{now}]*bas[len-1])*seed+a[pos_{now}]$ 。找到就 $break$ ,所有循环同构都不满足就 $return$ 。

upd:wcy学号就是个除了吉利一无是处的花瓶(

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
const int maxn = 5e6 + 5;
const int mod = 998244353;
char s[maxn]; int n;
int seed[2]={*,18271131};
// 嘿嘿第一个模数不给看了 谢谢wcy学号
int hs[2][maxn],bas[2][maxn];
void init(){
bas[0][0]=bas[1][0]=1;
rep(j,0,2) rep(i,1,n+1){
bas[j][i]=1ll*bas[j][i-1]*seed[j]%mod;
hs[j][i]=1ll*hs[j][i-1]*seed[j]%mod+s[i]-'a'+1;
if(hs[j][i]>=mod) hs[j][i]-=mod;
}
}
int getsum(int j,int l,int r){
int res=hs[j][r]-1ll*hs[j][l-1]*bas[j][r-l+1]%mod;
if(res<0) res+=mod; return res;
}
int check(int x){
int len=n/x,q[2];
q[0]=getsum(0,1,len);
q[1]=getsum(1,1,len);
rep(i,2,x+1){
int l=(i-1)*len+1,r=i*len,ff(0);
int p[2]; rep(j,0,2) p[j]=getsum(j,l,r);
if(p[0]==q[0]&&p[1]==q[1]) continue;
rep(k,1,len){
rep(j,0,2){
int ind=(i-1)*len+k;
int sub=1ll*(s[ind]-'a'+1)*bas[j][len-1]%mod;
p[j]=1ll*(1ll*p[j]-sub+mod)%mod*seed[j]%mod+s[ind]-'a'+1;
if(p[j]>=mod) p[j]-=mod;
} if(p[0]==q[0]&&p[1]==q[1]){ ff++; break; }
} if(!ff) return 0;
} return 1;
}
int solve(){
sc(n); scs(s+1); init();
for(int i=1;i*i<=n;++i) if(n%i==0){
if(i!=1) if(check(i)) return puts("Yes");
if(i*i!=n) if(check(n/i)) return puts("Yes");
} return puts("No");
}
int main(){
int _; sc(_); while(_--) solve();
}

1011-Kidnapper’s Matching Problem

题意

给定长度分别为 $n$ 、$m$ 的 $a$ 、$b$ 数组,再给定数量为 $k$ 的集合 $S$ 。对于 $S$ ,定义 $2_{\oplus}^S$ 为 $S$ 所有子集的异或和集合。问有多少 $a$ 的长度为 $m$ 、起点为 $l$ 的连续子数组满足任意 $1\leq i\leq m$ 有 $a_{l+i-1}\oplus b_i \in 2_{\oplus}^S$ 。

思路

出题人:名字就暗示是 $kmp$ 了

求出线性基后将 $a$ 、$b$ 筛掉,剩下不能用线性基表示的部分仅当 $a$ 、$b$ 相等时可以消去,所以用剩下部分跑一遍 $kmp$ 求匹配数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int a[maxn],b[maxn],s[maxn];
int qpow(int a,int b){
int ans=1; while(b>0){
if(b&1) ans=1ll*ans*a%mod;
b>>=1; a=1ll*a*a%mod;
} return ans;
}
int nex[maxn];
void getnext(int* s,int len){
int i=0,j=-1/* ,len=strlen(s) */;
nex[0]=-1; while(i<len){
if(j==-1||s[i]==s[j]){
i++; j++; nex[i]=j;
} else j=nex[j];
}
}
int kmp(int *s1,int *s2,int len1,int len2){
int i=0,j=0,ans(0); getnext(s2,len2);
// int len1=strlen(s1),len2=strlen(s2);
while(i<len1&&j<len2){
if(j==-1||s1[i]==s2[j]){ i++; j++; }
else j=nex[j];
if(j==len2){
ans+=qpow(2,i-len2);
if(ans>=mod) ans-=mod;
j=nex[j];
}
} return ans;
}
int d[32];
void insert(int x){
dep(i,30,0) if((x>>i)&1){
if(!d[i]){ d[i]=x; return; }
else x^=d[i];
}
}
void slove(int *s,int len){
rep(i,0,len) dep(j,30,0)
if(d[j]&&((s[i]>>j)&1)) s[i]^=d[j];
}
int solve(){
int n,m,k,x; mst(d,0);
sc(n),sc(m),sc(k);
rep(i,1,n+1) sc(a[i]);
rep(i,1,m+1) sc(b[i]);
rep(i,1,k+1) sc(x),insert(x);
slove(a+1,n); slove(b+1,m);
return pf("%d\n",kmp(a+1,b+1,n,m));
}
int main(){
int _; sc(_); while(_--) solve();
}