今天是COCI专场
T1 PAVORI
题意
从\(1-n\)的所有数中选出若干组两两互质的二元组，使得数轴上的\(1-n\)之间的区间被完全覆盖的方案数
解决
容易想到先排序然后再dp，定义\(dp[i][j]\)为处理完了前\(i\)个组覆盖了\(1-j\)的区间的方案数
转移
考虑当前这个区间选与不选
\[\left\{ \begin{aligned} 不选：dp[i][j]+=dp[i-1][j]\quad\quad\quad\quad\quad\quad\quad\\ 选：\left\{ \begin{aligned} if(a[i].l<=j)dp[i][a[i].r]+=dp[i][j]\\ else\quad dp[i][j]+=dp[i-1][j]\quad\quad\quad\quad \end{aligned} \right.\\ \end{aligned} \right. \]你可能会问这里面选的情况和不选的第二种情况不是重复的吗？？？当然是重复的，但是意义完全不一样，画个图就知道了
上面的两个\(j\)虽然是相同的，但是我可以选一个卵用没有的蓝色区间，这也可以构成一种新的方案
这样随便处理一下边界条件，注意一下小细节就能过了
\(Code\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=30;
const int MOD=1e9;
int n;
int gcd(int x,int y){return x%y==0?y:gcd(y,x%y);}
struct Par{int l,r;}a[maxn*maxn];int cnt;
bool cmp(Par a,Par b){return a.r<b.r;}
long long dp[maxn*maxn][100];/*用了i个覆盖了1~j*/
void pre()
{
dp[0][1]=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(gcd(i,j)==1)a[++cnt].l=i,a[cnt].r=j;
}
int main()
{
// freopen("parovi.in","r",stdin);
// freopen("parovi.out","w",stdout);
scanf("%d",&n);
pre();
/*
选：可以拼-更新 不能拼-直接从上个阶段继承
不选：直接继承
*/
sort(a+1,a+cnt+1,cmp);
// for(int i=1;i<=cnt;i++)
// printf("%d %d\n",a[i].l,a[i].r);
for(int i=1;i<=cnt;i++)/*枚举用的二元组数量*/
for(int j=1;j<=n;j++)/*枚举当前到的*/
{
dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
if(j>=a[i].l)dp[i][a[i].r]=(dp[i][a[i].r]+dp[i-1][j])%MOD;
else dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
}
// for(int i=1;i<=cnt;i++)
// {
// for(int j=1;j<=n;j++)
// printf("dp[%d][%d]:%lld\n",i,j,dp[i][j]);
// }
printf("%lld",dp[cnt][n]);
return 0;
}
T2 \(geppetto\)
解决问题
就是两个冲突的位置不能出现在一起，注意到这题\(N\)特别小，所以可以直接枚举二进制数就行，但是\(m\times 2^n\)的复杂度感觉是无法通过此题的（没试过），所以要加一个小小的优化，先贴代码再讲。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
int n,m;
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while('0'<=c&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int c[maxn];
int main()
{
// freopen("geppetto.in","r",stdin);
// freopen("geppetto.out","w",stdout);
double start=clock();
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
c[i]+=(1<<(x-1))+(1<<(y-1));
}
sort(c+1,c+m+1);
long long ans=0;
for(int i=0;i<(1<<n);i++)
{
int flag=1;
for(int j=1;j<=m&&c[j]<=i/*重要的优化*/;j++)
{
if((i&c[j])==c[j])
{
flag=0;
break;
}
}
if(flag)ans++;
}
printf("%lld",ans);
double end=clock();
printf("\n%lf",end-start);
return 0;
}
\(c[j]<=i\) 的时候就\(break\)是为什么呢，因为这个时候我们枚举的\(c[j]\)大于\(i\)，即一定有一位和\(i\)是不一样的，由于\(c[j]\)中至多只有两个\(1\)，而其中又一定有一个和\(i\)不一样，所以枚举更大的数就更没有意义了
T3 \(savez\)
说实话这道题真没有想到一点做法考试的时候，但是后面还算搞懂了，就是利用动态开点的字典树来节省空间，而结合子序列的\(dp\)做法来求最大值
解决方法
考虑怎么判断一个字符串为另一个字符串的的前缀和后缀。我们有一个很妙的做法：把字符串 s1⋯n 正反合在一起组成 n 个字符二元组，即 (s1,sn)(s2,sn−1)…(sn,s1)，那么这样就只用判断 xj 组成的二元组是否是 xi 的二元组的前缀就好了。
对于这些二元组，我们可以直接建 Trie，把每个字符串的二元组当成一个字符集为 26×26 的字符串插入，在插入的过程中如果当前节点是某个字符串的结尾就直接进行 dp，并在插入完时的结点记录此字符串编号即可
贴代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,ans=-1;
const int maxn=2e6+10;
int dp[maxn],rec[maxn];char s[maxn];int cnt=0;
unordered_map<int,unordered_map<int,int>>rt;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
int p=0;
for(int j=0;j<strlen(s);j++)
{
dp[i]=max(dp[i],dp[rec[p]]+1);
int w=(s[j]-'A')*26+(s[strlen(s)-j-1]-'A');
if(rt[p].find(w)==rt[p].end())rt[p][w]=++cnt;
p=rt[p][w];
}
dp[i]=max(dp[i],dp[rec[p]]+1);
ans=max(ans,dp[i]);rec[p]=i;
}
printf("%d",ans);
return 0;
}
T4 DRŽAVA
概要
这道题其实很简单的啊，虽然机房里只有孙巨做出来了，但是我还是轻松拿捏它的啊，其实你要是认真分析一下就知道这题肯定不是动态规划题，然后还要排除数论什么的，对吧？这下范围就小很多了，像我们这种强者啊一般都是直接贴代码的，看得懂就看，看不懂才是正常的，毕竟我这种方法是牛的，必须顶。
点击查看代码
Û®vçÍ·ë}¸ßÍwëÝ·Ûn¼ß]9Ûßw×^·×Nw×]w×]6÷½õ×õÛ]¼ënzÛ÷×M7×Nv÷ݸë}uë}vÛ}uëmößnwïMü×}»ã]=ßÝwÛ¾5Û~5×öã~úß½wÛúëvßnwómýçmöÛvßöïtã]ºßn·÷Î5ÓM¹ómûÛ®vß½º×nµÛwÛ®5ÓMüã}»ã]·ã]yßn7ïû×n¼ß]9ÛßwÛ½ûß~üßn¸×^8×m7Ûý÷vç}·ßθ×^·Ûü×vï}¸ß®x×mwÛÍûÓvÛ}¸ß®x×O7Û¾5Ó]ýó}»ßÝ8×n·ÛýótÓ}»ßÍ7ë·ë}»ã]¶ã]7Û}·Û~5ÛÎ5Ómöçtó<Û÷Û®5×Þ5ÛÍöëtÓu÷}¹ß®·÷möó~ö߯vã½·ïo5ÛÍvß½öï4ã]wßo7ïmú÷}¼ß½7ïM·Ûn=Û}¶ãÝ·ëmúßnø×m¸×Mößmºó}tço}ß]zß]9ß]uß]tÛÞ÷×^7×mvó¹ën;ß]4ß]9Ûßvãõ×õÛmõ×·Û}¹ß½7ó]öït÷ußnø×mø×^wÛûë~õßnwëýÛ}¹ßÍ·÷·Ûn<Û~¶÷ݽï}uã}tÓn|ÛvëMºß}vÓ}t÷}tómöß]|ß]5ß]xß]yß]9ß]uß]tÛv߸÷n:Û6ß·Û}t×}uÓo}ß]uß]4ß]9ß]tß]7Ûvßõ×½õ×õÓm¸çnzÛ~6ë}ºÛn´ß]=ß]yß]7ßn÷óN5×}öï6ã]{Û}·×M·×O6÷½õÓ}º×møÛvß·Û}uç}t×}uã}uó}tço}ß]5Û½öëͺ×mýÛvãÍ·÷möÛß7×^7×Nw×Mw×M¶ë]·ã}»ã]·ã]yßn7ïû×n¼ß]9Ûßvß·Û}uë}t×}t÷}uÛ}tóo{ß]zß]5Û½öëͺ×møÛvçm·ãmöÛÞö÷Ýõ×õÓõ×]õ×Mº×møß]}ß]5Ûß6ß·Û}uï}uã}tónµÛ~7×N7×^·×^·×]¶ç͸ïn;ß]{ß]xß]<Û¶÷Ýõ×M¸ïnvÛ7×^w×Mw×M·×^öï·ãmöÛ¶ëMõÓõ×õÓ]õÓÝ·Û}tóo{ß]µß]uß]{ß]zÛv߸ómøÛ¶ëM½ó}uï}uë}uë}u×}uÓmöÛßw×]w×O7×]w×^6ë]·ãmùÛ½6ïM¹ënzÛ6ãÍ·ãmöÛÞö÷Ýõ×õÓõ×]õ×Mº×møß]}ß]5Ûß6ß·Û}uï}uã}tónµÛ~6ß·Û}uç}tç}vÛ}t×nµÛ~6ç]¸ómø۶߽öëtã~ùßnwóÝüÓmûß^÷ëÎ5×öëuãvÓ}ºßßx×nwÛ}üëuë}¸ßÍx×n÷Û®5ÛN5×möïuó{ß^÷ëÎ5×öã5ß½÷Û¾5×~5×]ößvóvï}»ß¯8×o7Û®5ÓMûÓ}{߯8×^·Û5Ûûã}»ã]vã]xßnø×]ø×]wÛ~5ÛÎ5Û½öïuó{ßn8×nw뽺Ón;Ûß7×^÷×^·×^·×]w×]6ëmºÓ}tã}uãn;Û¶ëM¸ï}tç}uë}t×}t÷n¶Û7×^w×]w×^÷×^6÷ÝõÓ]·Û}uÓo{ß]=ß]5Ûvßöï4ã]wßn÷ón5×½öïvßuç}¸ß¾·ï]ºó}tço}Û~6ßmõÓ½÷}u×}uÓnµÛ~6ß·Û}uï}uã}tónµÛ~6߸ïn¶Û6ã½õÓÝõ×õÓ}öï4ã]wßn÷ón5×½ºØ
``
</details>