今日主要是杭电多校
今日一共过了6题
鸡爪
首先我们知道 n n n个边最多可以构造 n / 3 n/3 n/3个鸡爪。
构造方法多样,但是如果想要寻找字典序最小的构造方案,不那么容易。
显然地,如果边的数量不是3的整数倍,那么一定就是让多余的边向1连,这是字典序最小的必要条件。
不难发现如果想要字典序最小,那么一定是尽可能让小的数字连接尽可能多的边。
一共n/3个鸡爪,那么一定是前n/3个数字构成鸡爪
1连接的边要尽可能多,所以我们先让1向其他点连边,可以推出1一共要连边到 n / 3 + 3 n/3+3 n/3+3号点,其中1号点和后面三个点构成鸡爪,前面 n / 3 n/3 n/3个点自己构成鸡爪。
我们采取以下策略:
让四号点到 n / 3 n/3 n/3号点都跟2号和3号连边。
让2号跟后面的两个个点连边,3号跟二号以及后面的一个点连边。
这样能保证是最优的,因为2号点和3号店的利用率达到了最大。
但是这种情况是4个及以上鸡爪的情况。
对于前面的情况,我们手摸特判即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+100;
int n;
struct Node{
int l,r;
}ans[N];
int cnt = 0;
bool cmp(Node x,Node y){
if (x.l == y.l) return x.r < y.r;
else return x.l < y.l;
}
void Work(){
int nn;
cin>>nn;
if (nn == 1){
cout<<1<<' '<<2<<endl;
return;
}
if (nn == 2){
cout<<1<<' '<<2<<endl<<1<<' '<<3<<endl;
return;
}
cnt = 0;
if (nn%3 == 0) n = nn;
else n = (nn/3)*3;
int le = n/3-1;
for (int i = 2; i <= n/3+3; i++) ans[++cnt] = {1,i};
int Max = n/3+3;
le = nn-n;
if (n/3 == 3){
for (int i = Max+1; i <= Max+le; i++) ans[++cnt] = {1,i};
ans[++cnt] = {2,5}; ans[++cnt] = {2,4};
ans[++cnt] = {2,3}; ans[++cnt] = {3,4};
}
else if (n/3 <= 2){
for (int i = Max+1; i <= Max+le; i++) ans[++cnt] = {1,i};
if (n/3 >= 2)for (int i = 2; i <= min(4,n/3); i++) ans[++cnt] = {i,i+1},ans[++cnt] = {i,i+2};
if (n/3 >= 5) ans[++cnt] = {2,5},ans[++cnt] = {5,6};
if (n/3 > 5)
for (int i = 6; i <= n/3; i++) ans[++cnt] = {2,i},ans[++cnt] = {3,i};
}
else{
for (int i = Max+1; i <= Max+le; i++) ans[++cnt] = {1,i};
for (int i = 4; i <= n/3; i++) ans[++cnt] = {2,i},ans[++cnt] = {3,i};
ans[++cnt] = {2,n/3+1}; ans[++cnt] = {2,n/3+2};
ans[++cnt] = {2,3}; ans[++cnt] = {3,n/3+1};
}
sort(ans+1,ans+cnt+1,cmp);
for (int i = 1; i <= cnt; i++) cout<<ans[i].l<<' '<<ans[i].r<<endl;
return;
}
int main(){
int t; cin>>t; while (t--) Work();
return 0;
}
在 A 里面找有 C 的 B
对于b串进行hash/kmp筛选出可能得a串
在将a串放入trie树中跑ac自动机即可。
是一道板题
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#include<string.h>
#pragma GCC optimize(2)
//#include<sort>
using namespace std;
long long mod=100663319,base=131;
const int N=1e5+10;
bool ok;
int T,n,m,minn;
int jsq;
string s1,s2;
struct st{
string s1,s2;
int id;
}a[N],b[N];
int c[N*5][30];
int cnt = 0;
bool vis[N*2];
long long f[N],g[N],now,Base[N];
long long get_hash(int l,int r){
return (f[r]-(f[l-1]*Base[r-l+1]%mod)+mod)%mod;
}
vector < int > num[N*5];
int fail[N*5];
int ti[N*5][30];
#define pb push_back
void Build(string s,int id,int op){
int len = s.size();
int now = 0;
for (int i = 0 ; i < s.size(); i++) {
int X = s[i]-'a';
// if (ti[now][X]!=T) ti[now][X] = T , c[now][X] = 0;
if (!c[now][X]) c[now][X] = ++cnt;
now = c[now][X];
}
num[now].pb(id);
}
vector < int > ans;
void Do(){
queue < int > q;
for (int i = 0; i < 26; i++)
if (c[0][i]) q.push(c[0][i]),fail[c[0][i]] = 0;
while (q.size()){
int x = q.front(); q.pop();
for (int i = 0; i < 26; i++)
if (c[x][i]) fail[c[x][i]] = c[fail[x]][i],q.push(c[x][i]);
else c[x][i] = c[fail[x]][i];
}
}
int main(){
// freopen("1011.in","r",stdin);
// freopen("10111.out","w",stdout);
Base[0]=1ll;
for (int i=1;i<=N;i++)Base[i]=(Base[i-1]*base)%mod;
scanf("%d",&T);
while (T--){
scanf("%d",&n);
cin>>s1>>s2;
minn=s2.size();
for (int i=1;i<=minn;i++){
g[i]=(g[i-1]*base%mod)+(s2[i-1]-'a')%mod;
}
jsq=0;
for (int i=1;i<=n;i++){
cin>>a[i].s1>>a[i].s2,a[i].id = i;
m=a[i].s2.size();
ok=false;
for (int j=1;j<=m;j++){
f[j]=((f[j-1]*base%mod)+(a[i].s2[j-1]-'a'))%mod;
if(j>=minn){
now=get_hash(j-minn+1,j);
if (now==g[minn]){
ok=true;
break;
}
}
}
if (ok){
b[++jsq]=a[i];
}
}
for(int i = 1; i <= jsq; i++){
string S = b[i].s1;
Build(S,b[i].id,1);
}
Do();
int now = 0;
for (int i = 0 ; i < s1.size(); i++){
char ch = s1[i]-'a';
now = c[now][ch];
int t = now;
for (; t && vis[t] == 0; t = fail[t]){
for (int j = 0; j < num[t].size(); j++) ans.pb(num[t][j]);
num[t].clear();
vis[t] = 1;
}
}
if (ans.size()>0){
sort(ans.begin(),ans.end());
printf("%d",ans[0]);
for (int i = 1; i < ans.size(); i++) printf(" %d",ans[i]);
printf("\n");
}else printf("\n");
for (int i = 0; i <= cnt; i++) num[i].clear(),fail[i] = 0,vis[i] = 0;
for (int i = 0 ; i <= cnt; i++) for (int j = 0; j < 26; j++) c[i][j] = 0;
cnt = 0; ans.clear();
}
return 0;
}
/*
2
5
abcde a
a a
b a
c b
d a
e c
5
aaabbbccc xyz
ab xxxyzzzzyy
bccc aaaaxyza
abbbb xxxxyyz
aaaabbbcccc x
a xyzzzzzzzzz
*/
梦中的地牢战斗
发现k非常小,不难想到状压去表示打怪的情况
设 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示在(i,j)位置打怪情况为k的最优贡献。
本题还需要注意的一个点就是还有一个贷款问题。
其实我们可以把贷款看做补血,当生命值为负数的时候通过贷款拉高血线。
也就是怪物对我们的攻击我们可以理解为是负贡献。
同时注意到n和m都不大,我们可以对于每一个(i,j,k)都暴力建边然后跑一遍最长路即可。
注:本题我虽然能过大数据,但是由于我对于每种情况都进行了建边,所以我的复杂度还有多乘一个k,不足以过本题,主要理解一个思路。
#include<bits/stdc++.h>
using namespace std;
const int N = 40,M = (1<<10)+10,inf = 2e9+10;
int f[N*N*M];
int n,m,k;
int d;
struct Mon{
int x,y;
int a,b,c;// jiazhi gongjili juli
}a[N];
typedef pair < int , int > pii;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
vector < pii > e[N*N*M];
priority_queue < pii , vector < pii > , less < pii > > q;
map < pii , int > Mm;
bool vi[N*N*M];
int D(int x,int y,int xx,int yy){
return abs(x-xx)+abs(y-yy);
}
bool Isz(int x,int y,int xk,int yk,int x0,int y0){
int mix = min(x,x0) , maxx = max(x,x0);
int miy = min(y,y0) , maxy = max(y,y0);
if (xk < mix || xk > maxx) return 0;
if (yk < miy || yk > maxy) return 0;
return 1;
}
int ca(int x,int y,int kk){
int x1 = (x-1)*m+y;
int yy = (1<<k);
return (x1-1)*yy+kk;
}
pii Calc(int x,int y,int kk,int xx,int yy){
int s = 0;
int K = kk;
int mix = min(x,xx),Max = max(x,xx);
int miy = min(y,yy),May = max(y,yy);
for (int i = 1; i <= k; i++){
int xk = a[i].x , yk = a[i].y;
if ((kk>>(i-1))&1) continue;
if (Isz(xx,yy,xk,yk,x,y) == 0) continue;
K|=(1<<(i-1));
s+=a[i].a;
}
for (int i = 1; i <= k; i++){
int mx = a[i].x , my = a[i].y;
if ((K>>(i-1))&1) continue;
if (D(xx,yy,mx,my) <= a[i].c) s-=a[i].b;
}
return mp(s,K);
}
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
int ans = -inf;
void Sp(int x){
queue < int > Q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (f[ca(i,j,x)] != -inf) Q.push(ca(i,j,x)),vi[ca(i,j,x)] = 1;
while (Q.size()){
int x = Q.front(); Q.pop(); vi[x] = 0;
ans = max(ans,f[x]);
for (int i = 0; i < e[x].size(); i++){
int y = e[x][i].fi , v = e[x][i].se;
if (f[x]+v <= f[y]) continue;
f[y] = f[x]+v; if (!vi[y]) vi[y] = 1,Q.push(y);
}
}
}
void Work(){
ans = -inf;
cin>>n>>m>>k>>d;
for (int i = 1; i <= k; i++){
int x,y,aa,b,c; cin>>x>>y>>aa>>b>>c;
a[i] = {x,y,aa,b,c};
Mm[mp(x,y)] = i;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int kk = 0; kk < (1<<k); kk++){
int x = ca(i,j,kk);
for (int op = 0; op < 4; op++)
for (int dd = 1; dd <= d; dd++){
int ii = i+dx[op]*dd , jj = j+dy[op]*dd;
if (ii < 1 || ii > n || jj < 1 || jj > m) continue;
if (Mm[mp(ii,jj)] && ((kk>>(Mm[mp(ii,jj)]-1))&1) == 0) continue;
pii v = Calc(i,j,kk,ii,jj);
int y = ca(ii,jj,v.se);
e[x].pb(mp(y,v.fi));
}
}
int sx,sy; cin>>sx>>sy; int sk = 0;
int St = ca(sx,sy,sk);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int kk = 0; kk < (1<<k); kk++) f[ca(i,j ,kk)] = -inf , vi[ca(i,j,kk)] = 0;
f[St] = 0;
for (int i = 0; i < (1<<k); i++) Sp(i);
cout<<ans<<endl;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int kk = 0; kk < (1<<k); kk++) e[ca(i,j,kk)].clear();
while (q.size()) q.pop();
Mm.clear();
}
int main(){
freopen("1002.in","r",stdin);
freopen("1002.out","w",stdout);
int t; cin>>t; while (t--) Work();
return 0;
}
/*
2
3 5 7
6
2 2 876 61 6
3 3 3177 79 6
1 2 1735 77 6
2 3 5600 58 7
2 1 9926 92 4
1 1 4742 100 7
1 5 6528 62 7
3 5
*/