【比赛】【树上路径(phantasm)】
路径 比赛 树上
2023-06-13 09:11:52 时间
大家好,又见面了,我是你们的朋友全栈君。
—恢复内容开始—
题目大意:
求 1, 2, …, n 有多少个长为 m 的子序列 a,
满足
a1 = 1,am = n
∀i, ai+1 − ai ≥ k
保证这样的子序列存在。只需判断方案数的奇偶性。数据有 T 组。 n, m, k ≤ 109 , T ≤ 2 × 106 .
//dfs枚举集合
//复杂度预估 O(T*2^n)
//不用数组 得分30
//针对前6个点
#include<cstdio>
#include<cstdlib>
using namespace std;
int t,n,m,k;
int sum;
void dfs(int pos,int x)
{
if(pos==m)
{
if(x==n)
sum=(sum+1)%2
return ;
}
for(int i=x+k;i<=n;i++)
dfs(pos+1,i);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
sum=0;
dfs(1,1);
if(sum) printf("Yes\n");
else printf("No\n");
}
return 0;
}
对于第8个点
{
scanf("%d%d%d",&n,&m,&k);
if(m==2) printf("Yes\n");
else if(m==3)
{
sum=n-(k<<1);
if(sum%2==1) printf("Yes\n");
else printf("No\n");
}
else
{
sum=0;
dfs(1,1);
if(sum) printf("Yes\n");
else printf("No\n");
}
}
//2记忆化
//dfs->dp
//f[i][j]表示第i步,位置为j
//因为状态转移方程中的k为变量,所以还是得分k的大小来dp
//f[k][i][j] // 55 分
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int tt,nn,mm,kk;
int f[203][203][203];//1:true
inline int read()
{
int x=0;char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return x;
}
int dfs(int n,int m,int k)
{
if(f[k][m][n]!=-1) return f[k][m][n];
if(m==1) return f[k][m][n]=0;
if(m==2 )
if(n>k) return f[k][m][n]=1;
else return f[k][m][n]=0;
int s=k ,t=n-k*(m-2),as=0;
for(int i=s;i<=t;i++)
as=(as+dfs(n-i,m-1,k))%2;
return f[k][m][n]=as;
}
int main()
{
tt=read();
memset(f,-1,sizeof(f));
for(int i=1;i<=tt;i++)
{
nn=read(),mm=read(),kk=read();
if(mm==2) printf("Yes\n");
else if(mm==3)
{
int sum=nn-(mm-1)*kk;
if(sum%2!=0) printf("Yes\n");
else printf("No\n");
}
else if( dfs(nn,mm,kk) ) printf("Yes\n");
else printf("No\n"); }
return 0;
}
90分算法(n,m,k<=5000)
推式子。
注意到第二条约束与 a 的差分序列有关,考虑统计差分序列 bi = ai+1 − ai。
序列 b 需要满足
∀i, bi 是 [k, n] 上的整数
∑bi = n − 1
由于 a1 = 1 已确定,可以发现所有满足以上约束的长为 m − 1 的序列 b 与原来的序列 a 一一对应。
有限项的正整数序列的和确定时,其方案数可以用隔板法计 算,
所以构造 ci = bi − (k − 1) 来去除第一条约束,
序列 c 满足
∀i, ci 是正整数
∑m−1 ci = n − 1 − (m − 1)(k − 1)
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int t,nn,mm,kk;
struct node
{
//m=m-2
int id,n,m;//n=n-2-(m-1)(k-1)
bool operator < (const node & o) const
{
if(n!=o.n) return n<o.n;
else return m<o.m;
}
}ask[2000003];
bool ans[2000003],f[5003];
int main()
{
scanf("%d",&t);
for(int i=0;i<t;i++)
scanf("%d %d %d",&nn,&mm,&kk),
ask[i].n =nn-2-(mm-1)*(kk-1),ask[i].m =mm-2,ask[i].id =i;
sort(ask,ask+t);
int nw=0,nwn=1;
nn=ask[nw].n ;
f[0]=true;
while(nw<t)
{
for(int i=nwn;i<=nn;i++)
for(int j=i;j>=0;j--)
f[j]^=f[j-1];
nwn=nn+1;
while(ask[nw].n ==nn)
ans[ask[nw].id ]=f[ask[nw].m ],nw++;
nn=ask[nw].n ;
}
for(int i=0;i<t;i++)
if(ans[i]) printf("Yes\n");
else printf("No\n");
return 0;
}
100分算法
(解决两个1e9的超大点)
由 Lucas 定理,( n k ) ≡ 1 (mod 2)
当且仅当二进制下 k 的各 位都不大于 n 的对应位,即 n and k = k,
其中 and 为二进制按 位与。 复杂度:O(T)。
#include <cstdio>
#include <cstdlib>
using namespace std;
int t,n,m,k;
int main ()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
int a=n-(m-1)*(k-1)-2;
int b=m-2;
if((a&b)==b)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
转载于:https://www.cnblogs.com/xwww666666/p/11325852.html
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/139060.html原文链接:https://javaforall.cn
相关文章
- 网络分析最佳路径_局域网找不到网络路径
- maven本地仓库默认路径_maven本地仓库
- 浏览器上传文件的三种路径
- DCDC Buck拓扑的大电流路径
- jquery 路径动画贝塞尔动画详解编程语言
- 管理Oracle实例:最佳实践路径(管理Oracle实例)
- 路径配置Linux系统中PATH路径的配置(linux系统path)
- Linux 文件分割:分治路径难行(linux将文件分割)
- Linux下如何设置jar包路径(linuxjar包路径)
- 极简指南:寻找Linux下载路径(linux在哪里下载)
- 载基于c语言与MySQL数据库的图片路径下载方案(c mysql图片路径下)
- 如何使用CMD进入MySQL路径(cmd进入mysql路劲)