20220922（种苹）
t1 [COCI2015-2016#6] PAROVI
最初思路
若选择二元组中不包含1，那Slavko只需选择2作为x即可对所有二元组满足a，b≥x；同样，若不包含n，则Slavko只需选择n作为x即可满足a，b<x。以此类推，我们可以发现只需使选择的二元组覆盖1-n的范围即可。那么暴力的思路就有了，每次选择一个二元组，覆盖该二元组的范围，例如：二元组{2，5}即覆盖2-5的范围，如果最后能覆盖完1-n的范围就统计答案，不过要注意一个二元组如{2，5}覆盖的范围其实是（2，5]而不是[2，5]。'('表示覆盖不到，'['表示能覆盖到，类似于开区间与闭区间。
最终思路
显然，这样的暴力是过不了的，所以考虑用dp优化暴力。因为要覆盖区间，考虑如何将区间加入到dp方程中。那么就考虑新区间与已覆盖区间时出现的情况，可以发现有两种情况：
-
新区间可以与旧区间合并。（就是拼在一起 [2，6]+[5，7]=[2，7]）
-
新区间无法旧区间合并。（[2，6]+[5，7]=[2，6] [5，7]）
那我们就可以用不断加入新区间的方式dp，而从头开始覆盖的方式无疑是最容易转移的。但这样我们就需将二元组右端点从小到大排序。所以动态转移方程的定义就出来了dp[i][j]表示选择到第i个二元组，能覆盖到1-j区间的方案数。dp状态转移的方程也就顺利成章地推出来了。（l[i]为二元组左端点，r[i]为二元组右端点）
若l[i]<=j，则该区间可以合并：若选，dp[i][r[i]]+=dp[i-1][j];
若不选，dp[i][j]+=dp[i][j]。
若l[i]>j,则该区间无法合并，但依然可以贡献答案。可以证明该无法合并的区间在之后一定能被覆盖，因为我们已经提前将二元组右端点从小到大排序了，dp[i][j]+=dp[i][j]。
代码如下:
#include<iostream>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int mod=1000000000;
int n;
int l[100000],r[100000],g;
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
inline ll getin(ll zt,int i){
for(ll j=l[i]+1;j<=r[i];++j){zt|=(1<<(j-1));}
return zt;
}
ll dp[10000][22];
int main(){
in(n);
fo(i,1,n)
fo(j,1,i-1)
if(gcd(j,i)==1){l[++g]=j,r[g]=i;}
dp[1][r[1]]=dp[1][1]=1;
fo(i,1,g){
fo(j,1,n){
dp[i][j]+=dp[i-1][j],dp[i][j]%=mod;
if(l[i]<=j)dp[i][r[i]]+=dp[i-1][j],dp[i][r[i]]%=mod;
else dp[i][j]+=dp[i-1][j],dp[i][j]%=mod;
}
}
out(dp[g][n]);
return 0;
}t2 [COCI2015-2016#2] GEPPETTO
思路
看到这道题我首先就打了个表。。。格，随后就产生了暴力的思路。只要选择的材料不冲突，就是一个方案。那我们就可以枚举材料，判断是否可行，可行就方案数+1。而枚举材料这个过程显然可以用回溯法解决，不过为了避免出现{1，2，3}和{2，1，3}这种重复的情况，我们让每次枚举都从上次的材料编号+1开始枚举。而我们判断一个方案是否可行，又需要在回溯法中进行操作，而后加入的状态因为回溯先弹出，那显然可以通过栈的方式维护。然后。。。就没有然后了。
代码如下:
#include<iostream>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int M=405;
int n,m;
int a,b;
bool v[M][M];
ll ans;
int s[30],top;
inline void push(int x){s[++top]=x;}
inline void pop(){--top;}
inline int get(){return s[top];}
inline bool check(int x){
fo(i,1,top)
if(v[s[i]][x])return 0;
return 1;
}
inline void dfs(int x,int last){
if(x>n)return;
fo(i,last+1,n){
if(!check(i))continue;
if(x>1)++ans;
push(i);
dfs(x+1,i);
pop();
}
return;
}
inline void mswap(int &a,int &b){
int c=a;
a=b;
b=c;
}
int main(){
in(n),in(m);
fo(i,1,m){
in(a),in(b);
if(a>b)mswap(a,b);
v[a][b]=1;
}
++ans;
ans+=n;
dfs(1,0);
out(ans);
return 0;
}t3 [COCI2015-2016#2] SAVEZ
思路
这道题很容易想到hash。将每个字符串的正逆序hash值存储下来，然后暴力对比，得出答案。但这样并不能ac。
所以考虑如何优化比对的过程。这个过程与ac自动机有一定的相似性。所以可以思考用ac自动机的思路优化。有一个很妙的方法就是将字符串的前后缀存入字典树中。如果之后的字符串也经过了已经建好的边，就可以改变答案。最后取个最大值即可。
代码如下:
#include<iostream>
#include<cstring>
#include<unordered_map>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
unordered_map <int,unordered_map<int,int> >tr;
int n;
char c[2000005];
int tot;
int dp[2000005];
int pos[2000005];
int ans;
int main(){
in(n);
fo(i,1,n){
scanf("%s",c+1);
int len=strlen(c+1);
int now=0;
fo(j,1,len){
dp[i]=max(dp[i],dp[pos[now]]+1);
int has=(c[j]-'A')*26+c[len-j+1]-'A';
if(tr[now].find(has)==tr[now].end())tr[now][has]=++tot;
now=tr[now][has];
}
if(pos[now])dp[i]=max(dp[i],dp[pos[now]]+1);
pos[now]=i;
ans=max(ans,dp[i]);
}
out(ans);
return 0;
}