Day1 T1
签到题，模拟一下随便写就能过。
不过小心像我一样表打错傻逼的调了10min。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int La=,Lb=,N=;
int xl_a[]={},xl_b[]={};
int check[][]={{,-,,,-},{,,-,,-},{-,,,-,},{-,-,,,},{,,-,-,}};
int main(void)
{
freopen("rps.in","r",stdin);
freopen("rps.out","w",stdout);
scanf("%d%d%d",&N,&La,&Lb);
for(int i=;i<=La;i++)scanf("%d",&xl_a[i]);
for(int i=;i<=Lb;i++)scanf("%d",&xl_b[i]);
int a=,b=,ans_a=,ans_b=;
for(int i=;i<=N;i++)
{
a=xl_a[i%La];
if(!(i%La))a=xl_a[La];
b=xl_b[i%Lb];
if(!(i%Lb))b=xl_b[Lb];
if(check[a][b]==){ans_a++;continue;}
if(check[a][b]!=){ans_b++;;continue;}
}
printf("%d %d",ans_a,ans_b);
return ;
}
T2
没什么难度……不知道为什么能卡当时的我只拿70分。
大概是不知道n个点n-1条边就是树？
最开始写代码的时候没考虑兄弟节点的情况……后面紧急补上去了，还好发现了不然岂不是又得炸。
一涉及到取模我的代码风格就变得乱七八糟。
简述一下，我们对这棵树从1开始dfs，每到一个节点，就先更新答案（和它父亲的父亲）。
然后枚举它的儿子节点，记录两个参数，max_son和tot，max_son是它儿子节点中权值最大的那个，tot是它所有儿子的权值和。
max_son是更新第一个最大值的答案的，tot是更新第二个答案的。
顺便提醒一下，因为题面上说的是有序点对，所以说我们每次更新第二个答案的时候都要记住乘个2……【血泪教训】
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
struct lb
{
int nw;
int nxt;
};
lb line[];
int n=,cnt=,val[]={},head[]={};
int fa[]={},ans1=,ans2=;
void add(int f,int t);
void dfs(int nw);
int main(void)
{
freopen("link.in","r",stdin);
freopen("link.out","w",stdout);
scanf("%d",&n);
int a=,b=;
for(int i=;i<=n-;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=;i<=n;i++)scanf("%d",&val[i]);
fa[]=;
dfs();
printf("%d %d",ans1,ans2);
return ;
} void add(int f,int t)
{
line[++cnt].nw=t;
line[cnt].nxt=head[f];
head[f]=cnt;
return;
} void dfs(int nw)
{
if(nw>n)return;
if(fa[fa[nw]])
{
ans1=max(ans1,val[nw]*val[fa[fa[nw]]]);
ans2+=val[nw]*val[fa[fa[nw]]]*;
ans2%=;
}
int next=,max_son=,tot=;
for(int i=head[nw];i>;i=line[i].nxt)
{
next=line[i].nw;
if(next==fa[nw])continue;
ans1=max(ans1,val[next]*max_son);
ans2+=(tot%)*val[next]*;
ans2%=;
max_son=max(max_son,val[next]);
tot+=val[next];
tot%=;
fa[next]=nw;
dfs(next);
}
return;
}
T3
我和昨年一样没有长进【不还是多得了五分的】
剩下的都是TLE。
代码风格无论怎么说还是变了一些的。
这题就是个背包，完全=A=，但是我写得丑写不过……
昨年代码↓
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
ifstream fin("bird.in");
ofstream fout("bird.out");
bool jz[][]={};//0表示可通行,1表示有管道
int ss[][]={};//0表示点击后上升,1表示向下坠落
int DP[][]={};//DP[i][j]表示在x坐标为i,y坐标为j下最小点击数
bool gd[]={};//记录每一ｘ坐标是否有管道
int Lx=,Ly=,Gds=;
int main(void)
{
fin>>Lx>>Ly>>Gds;
for(int i=;i<Lx;i++)fin>>ss[][i]>>ss[][i];
int Gx=,Up=,Down=;
for(int i=;i<=Gds;i++)
{
fin>>Gx>>Down>>Up;
for(int j=;j<=Down;j++)jz[Gx][j]=true;
for(int j=Ly;j>=Up;j--)jz[Gx][j]=true;
gd[Gx]=true;
}
memset(DP,/,sizeof(DP));
for(int i=;i<=Ly;i++)DP[][i]=;
int ans=0x7fffffff,tgs=,nxt=;
bool pd=false;
for(int i=;i<=Lx;i++)
{
ans=0x7fffffff;
pd=false;
for(int j=;j<=Ly;j++)
{
if(DP[i][j]==)continue;
if(jz[i][j])continue;
pd=true;
if(!jz[i+][j-ss[][i]]&&j-ss[][i]>)//如果不点击下一回合也不会死亡
{
DP[i+][j-ss[][i]]=min(DP[i+][j-ss[][i]],DP[i][j]);
if(DP[i+][j-ss[][i]]<ans)ans=DP[i+][j-ss[][i]];
}
for(int k=;k<=Ly;k++)
{
nxt=k*ss[][i];//点击ｋ次后下一次上升的位置
if(nxt+j>Ly)nxt=Ly-j;
if(jz[i+][j+nxt])continue;
DP[i+][j+nxt]=min(DP[i+][j+nxt],DP[i][j]+k);
if(DP[i+][j+nxt]<ans)ans=DP[i+][j+nxt];
if(nxt==Ly-j)break;
}
}
if(!pd)break;
if(gd[i])tgs++;
}
if(tgs==Gds)fout<<"1\n"<<ans;
else fout<<"0\n"<<tgs;
return ;
}
今年的↓
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n=,m=,k=,bef[]={};
int up[]={},down[]={},dp[][]={};
bool check[][]={};
const int INF=;
int main(void)
{
freopen("bird.in","r",stdin);
freopen("bird.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++)scanf("%d%d",&up[i],&down[i]);
int a=,b=,c=;
for(int i=;i<=k;i++)
{
scanf("%d%d%d",&a,&b,&c);
for(int j=;j<=b;j++)check[a+][j]=;
for(int j=c;j<=m;j++)check[a+][j]=;
bef[a+]++;
}
for(int i=;i<=n;i++)bef[i]+=bef[i-];
memset(dp,0x7f,sizeof(dp));
for(int i=;i<=m;i++)dp[][i]=;
int u=,d=,mark=,ans=INF,loop=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(dp[i&][j]!=INF&&!check[i][j])
{
mark=i;
loop=max((m-j)/up[i]+,);
for(int k=;k<=loop;k++)
{
u=min(m,j+up[i]*k);
if(!check[i+][u])dp[(i+)&][u]=min(dp[(i+)&][u],dp[i&][j]+k);
if(i==n)ans=min(ans,dp[(i+)&][u]);
}
d=max(,j-down[i]);
if(d==)continue;
if(!check[i+][d])dp[(i+)&][d]=min(dp[(i+)&][d],dp[i&][j]);
if(i==n)ans=min(ans,dp[(i+)&][d]);
}
}
for(int j=;j<=m;j++)dp[i&][j]=INF;
}
if(mark<n)
{
printf("0\n%d",bef[mark]);
return ;
}
printf("1\n%d",ans);
return ;
}