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();
}