今年的NOIP提高组还是有很大难度的，至少我认为这样QAQ；
实际证明只是搞掉了D1T1，剩下的都是骗分？？？
D1 T1 玩具谜题：
这道题相对简单，根据题意进行模拟即可；
考试时忘了写: if(tmp==0) tmp=n; 貌似要掉好多分?；
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct your
{
int to;
char s[20];
}a[110000];
int n,m;
int tmp=1;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%s",&a[i].to,a[i].s);
}
for(int i=1;i<=m;i++)
{
int dx,dy;
scanf("%d%d",&dx,&dy);
if(dx==1)
{
if(a[tmp].to==0)tmp=(tmp+dy+n)%n;
else tmp=(tmp-dy+n)%n;
}
else
{
if(a[tmp].to==0)tmp=(tmp-dy+n)%n;
else tmp=(tmp+dy+n)%n;
}
if(tmp==0)tmp=n;
}
printf("%s",a[tmp].s);
}D1 T2 天天爱跑步
一名蒟蒻不会正解......据说骗分正解是DFS寻径？？？然而我用的O(n^2)暴力和他们用DFS的一样多啊......
考场骗分代码在此：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
struct your
{
int x,y;
}a[100100];
struct my
{
int x,y;
}b[100100];
int t[100100];
int temp[1000];
int ans[100100];
int checklian()
{
for(int i=1;i<=n-1;i++)
if(abs(a[i].x-a[i].y)!=1) return 0;
return 1;
}
void worklian()
{
for(int i=1;i<=m;i++)
{
int dx,dy;
scanf("%d%d",&dx,&dy);
for(int j=1;j<=n;j++)
if(dy>=dx&&j<=dy&&j>=dx&&t[j]==j-dx)
ans[j]++;
else
if(dy<=dx&&j>=dy&&j<=dx&&t[j]==dx-j)
ans[j]++;
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return ;
}
int checkt0()
{
for(int i=1;i<=n;i++)
if(t[i]!=0)return 0;
return 1;
}
void workt0()
{
int dx,dy;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&dx,&dy);
for(int j=1;j<=n;j++)
if(j==dx) ans[j]++;
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return ;
}
int checkdst()
{
for(int i=1;i<=m;i++)
if(b[i].x!=b[i].y) return 0;
return 1;
}
void workdst()
{
for(int i=1;i<=m;i++)
temp[b[i].x]++;
for(int i=1;i<=n;i++)
if(t[i]==0)ans[i]+=temp[i];
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return;
}
void workputong()
{
for(int i=1;i<=m;i++)
scanf("%d%d",&b[i].x,&b[i].y);
if(checkdst()) workdst();
else printf("2 0 0 1 1 1");
return ;
}
int main()
{
freopen("running.in","r",stdin);
freopen("running.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++)
scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)
scanf("%d",&t[i]);
if(checklian()) worklian();
else if(checkt0()) workt0();
else workputong();
fclose(stdin);
fclose(stdout);
return 0;
}D1 T3 换教室
Floyed+DP??? 然而考场写挂了?；
（有待完善）
D2 T1 组合数问题
考场上没想到正解，就硬生生的循环求阶乘，搞了点优化，貌似拿了不少分?；
比赛后才意识到竟然有组合数公式？？
愧对于LLQ啊 其实可以做的更好，比如说可以加入快速幂优化，边乘边模，还傻乎乎的先把分子算出来再判断......
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int t,k,n,m;
long long jisuan1(long long x,long long y)
{
long long p=1;
for(int i=x;i<=y;i++) p*=i;
return p;
}
long long jisuan2(int x)
{
long long p=1;
for(int i=1;i<=x;i++) p*=i;
return p;
}
int main()
{
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
scanf("%d%d",&t,&k);
for(int z=1;z<=t;z++)
{
int ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=min(i,m)&&i!=j;j++)
{
if(j+1<=i-j)
{
long long tmp=0;
tmp+=jisuan1(i-j+1,i);
if(tmp>=k&&tmp%k==0)
{
tmp/=jisuan2(j);
if(tmp%k==0&&tmp>=k) ans++;
}
}
else
{
long long tmp=0;
tmp+=jisuan1(j+1,i);
if(tmp>=k&&tmp%k==0)
{
tmp/=jisuan2(i-j);
if(tmp%k==0&&tmp>=k) ans++;
}
}
}
}
printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}⬆ 考场上的代码
⬇ 正解是杨辉三角形+前缀和
#include<cstdio>
#include<algorithm>
using namespace std;
int a[2500][2500];
int f[2500][2500];
int t,k,n,m;
int main()
{
scanf("%d%d",&t,&k);
for(int i=1;i<=2000;i++)
a[i][0]=a[0][i]=1;
for(int i=1;i<=2010;i++)
for(int j=1;j<=i;j++)
{
a[i][j]=(a[i-1][j-1]+a[i-1][j])%k;
if(!a[i][j])f[i][j]=1;
}
for(int i=1;i<=2000;i++)
for(int j=1;j<=2000;j++)
f[i][j]=f[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
for(int i=1;i<=t;i++)
` scanf("%d%d",&n,&m),printf("%d\n",f[n][m]);
}D2 T2 蚯蚓
当时考场上也没有什么太好的思路，只好骗了20分；
回来之后看到的正解如下：这道题需要开三个队列，一个数列存初始的蚯蚓，另外两个数列分别求切下蚯蚓的较长部分和较短部分，保持每个队列的单调递减，我听从了学长的建议，使用数组模拟队列。然后对于++q的问题，使用前缀和思想；
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[4][7510000];
int l[4],r[4];
int n,m,qsum,u,v,t;
int sum;
int cmp(int x,int y)
{
return x>y;
}
int findmax()
{
int maxi,maxx=-2001000000;
if(l[1]<=r[1]&&maxx<a[1][l[1]]) maxx=a[1][l[1]],maxi=1;
if(l[2]<=r[2]&&maxx<a[2][l[2]]) maxx=a[2][l[2]],maxi=2;
if(l[3]<=r[3]&&maxx<a[3][l[3]]) maxx=a[3][l[3]],maxi=3;
l[maxi]++;
return maxx;
}
void shuchu()
{
int k=0;
for(int i=1;i<=n+m;i++)
{
int nmp=findmax()+sum;
if(i%t==0) printf("%d",nmp);
}
return ;
}
void work()
{
int k=0;
long long temp1,temp2;
for(int i=1;i<=m;i++)
{
long long nmp=findmax();
nmp+=sum;
sum+=qsum;
temp1=nmp*u/v;
temp2=nmp-nmp*u/v;
a[2][++r[2]]=max(temp1,temp2)-sum;
a[3][++r[3]]=min(temp1,temp2)-sum;
if(i%t==0) printf("%lld",nmp);
}
printf("\n");
shuchu();
return ;
}
int main()
{
l[1]=l[2]=l[3]=1;
scanf("%d%d%d%d%d%d",&n,&m,&qsum,&u,&v,&t);
for(int i=1;i<=n;i++)
scanf("%d",&a[1][++r[1]]);
sort(a[1]+1,a[1]+r[1]+1,cmp);
work();
}D2 T3 愤怒的小鸟
状压DP？？？ 不会啊
现在会了
首先贪心 打一只也是打 打两只也是打 那么我们就要预处理出 f[i][j] 即包含i,j猪能打掉的猪的集合
然后DP
dp[s|f[i][j]]=min(dp[s|f[i][j]],dp[s]+1); dp[s|(1<<(i-1))]=min(dp[s|(1<<(i-1)],dp[s]+1);
但是会TLE 那我们就这样 找到第一只没有被打掉的猪(i) 然后再枚举j进行DP转移
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int time;
int n,m;
int f[200][020];
int dp[2621500];
struct your
{
double x,y;
}a[200];
double calc_a(double aa,double bb,double cc,double dd)
{
return ((dd/cc)-(bb/aa))/(cc-aa);
}
double calc_b(double tmp,double aa,double bb)
{
return (bb/aa)-tmp*aa;
}
double Fabs(double tmp)
{
return (tmp>0)?tmp:-tmp;
}
int main()
{
scanf("%d",&time);
while(time)
{
time--;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
double dx=calc_a(a[i].x,a[i].y,a[j].x,a[j].y);
double dy=calc_b(dx,a[j].x,a[j].y);
if(dx>=0) continue;
for(int k=1;k<=n;k++)
if(Fabs(dx*a[k].x*a[k].x+dy*a[k].x-a[k].y)<=1e-6)
f[i][j]|=(1<<(k-1));
}
for(int i=0;i<=(1<<n);i++) dp[i]=233333333;
dp[0]=0;
for(int s=0;s<(1<<n);s++)
for(int i=1;i<=n;i++)
if(!(s&(1<<(i-1))))
{
dp[s|(1<<(i-1))]=min(dp[s|(1<<(i-1))],dp[s]+1);
for(int j=i+1;j<=n;j++)
dp[s|f[i][j]]=min(dp[s|f[i][j]],dp[s]+1);
break;
}
printf("%d\n",dp[(1<<n)-1]);
memset(f,0,sizeof f);
}
return 0;
}