8.13 愉快且排名新高的杭电8
题意
给定长度为 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
代码
#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();
}
题意
给定在以原点为圆心的圆上三个点。问这三个点是顺时针还是逆时针。
思路
套了个求多边形面积的板子,判面积正负就过了。
代码
#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();
}
题意
给定 n 段限制,问能否找到可以满足每段限制的方案,方案之间差值最大为 k 。
思路
因为不会 dp 直接考虑贪心(确实不是 dp )。求出每段满足题意的 l 、r ,最后倒推回去。
代码
#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();
}
题意
给定半径为 n 的六边形网格图,可以任意选择起点,问不重复地走满全部网格且转弯最多的路径方案。
思路
团体智慧的聚集,小转画图,小庄造数据,小潘找规律写代码
分奇数和偶数进行分析
偶数时,直接从左上角开始从外到内的绕圈,最后会正好绕完
奇数时,可以视为前一个半径 (r - 2) 的图外面再多绕一圈,绕法与偶数相同
写的时候就先把半径为 3 和 4 的结果写好,完事拿着前一个绕就行了,节省时间可以打个不同位置的表来绕
嗯,花花大法好
奇数情况:
题意
给定串 s ,问能否均等地划分成 k 份,使得每份互为循环同构。
思路
备注:理论复杂度不低,但是很难卡满,O(能过) ,甚至没到 1s
枚举每个因数,对每个因数 check 。
求出第一块的哈希值,之后每块和第一块的对比。如果和第一块不同就枚举循环同构,递推求循环同构的哈希值,具体是 (hash-a[pos_{now}]*bas[len-1])*seed+a[pos_{now}] 。找到就 break ,所有循环同构都不满足就 return 。
upd:wcy学号就是个除了吉利一无是处的花瓶(
代码
#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();
}
题意
给定长度分别为 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 求匹配数即可。
代码
#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();
}