2018.01.26【GDOI2018】模拟A组 B组

今天的题比以往简单，然而我才240分~
100+100+40(估分100)+0(估分40)=240；
T1：【NOIP2014模拟11.2B组】超氧化钾
比赛时找找规律就好了。
https://jzoj.net/senior/#contest/show/2263/0
详细看：传送门

#include   
#include  
using namespace std;   
long long x,y,z;  
int main()  
{  scanf("%lld%lld",&x,&y); long long i,j;if(y<=100000)  {  for(i=1;i<=y;i++) z+=x%i;  printf("%lld\n",z);  return 0;  }  if(xlong long yy=0,l,r,p,q,num;  for(i=2;i;i++)  {  if(x/(i-1)<=100000)  {  yy=min(x/(i-1),y);  break;  }   l=x/i+1;  r=min(x/(i-1),y);  p=x%l;q=x%r;  num=r-l+1; if(num<=0) continue; z+=(p+q)*num/2;   }  for(i=1;i<=yy;i++)z+=x%i;  printf("%lld\n",z);return 0;  }   

T2:【NOIP2014模拟11.2B组】艰难的选择
https://jzoj.net/senior/#contest/show/2263/1
50分很水，100分就在59分的基础上，加一个记录这种前缀和第一次在什么地方出现就好了；

#include
#include
using namespace std;
int f[100001][2];
int sum[100001];
int n,ans,v,p;
int a[100001];
int main()
{scanf("%d",&n);int i;for (i=1;i<=n;++i) {scanf("%d",&a[i]);if(a[i]==0) a[i]=-1;}for (i=1;i<=n;++i) f[i][1]=f[i][0]=-1;for (i=1;i<=n;++i){sum[i]=sum[i-1]+a[i];if(sum[i]>0)v=0;else v=1;if(sum[i]>0)p=sum[i];else p=-sum[i];if(f[p][v]<0) f[p][v]=i;else ans=max(ans,i-f[p][v]);}printf("%d\n",ans);
}

T3：【NOIP2014模拟11.2B组】人品问题
https://jzoj.net/senior/#contest/show/2263/2
我觉得我没A这道题的原因跟这道题的题目很像。
简单的树形dp，但是我没有判一个点没有左儿子或者没有右儿子的情况：

#include
#include
#include
using namespace std;
long long f[101][101];
long long size[101];
long long son[101][2];
long long a[101];
long long n,k;
void dfs(long long t)
{if(son[t][0]) dfs(son[t][0]);if(son[t][1]) dfs(son[t][1]);size[t]=size[son[t][0]]+size[son[t][1]]+1;for (long long i=2;i<=min(k,size[t]);++i){if(son[t][0]&&son[t][1]){for (long long j=0;j<=min(k,size[son[t][0]]);++j)   if(i-j-1<=size[son[t][1]]) f[t][i]=max(f[t][i],f[son[t][0]][j]+f[son[t][1]][i-j-1]);}else {if(son[t][0]) f[t][i]=max(f[t][i],f[son[t][0]][i-1]);if(son[t][1]) f[t][i]=max(f[t][i],f[son[t][1]][i-1]);}f[t][i]+=a[t];}f[t][0]=0;f[t][1]=a[t];
}
int main()
{scanf("%d%d",&n,&k);++k;long long i,j;memset(f,128,sizeof(f));for (i=0;i<=k;++i) f[0][i]=0;for (i=2;i<=n;++i) scanf("%lld",&a[i]);for (i=1;i<=n;++i) scanf("%d%d",&son[i][0],&son[i][1]);dfs(1);printf("%lld\n",f[1][k]);
}

T4：【NOIP2014模拟11.2A组】福慧双修
https://jzoj.net/senior/#contest/show/2263/3
我的方法时在40分方法的基础上判断一下出的点和入的点在二进制下的一位不同。
就好了：

#include
#include
#include
using namespace std;
int last[40001],next[100001*2],tov[100001*2],len[100001*2];
int n,m,tot,head,tail,ans;
bool vis[40001];
int dis[40001];
int f[10000001];
void insert(int x,int y,int z)
{tov[++tot]=y;len[tot]=z;next[tot]=last[x];last[x]=tot;
}
void spfa(int p,int q)
{int head=0,tail=0,x,y,i;memset(dis,127,sizeof(dis));memset(vis,0,sizeof(vis));for (i=last[1];i;i=next[i]){if((tov[i]&p)==q){f[++tail]=tov[i];vis[tov[i]]=true; dis[tov[i]]=len[i];}}while (head!=tail){x=f[++head];for (i=last[x];i;i=next[i]){y=tov[i];if (dis[x]+len[i]y]&&y!=1){dis[y]=dis[x]+len[i];if (vis[y]==false){vis[y]=true;f[++tail]=y;}}if(y==1&&(x&p)!=q) ans=min(ans,dis[x]+len[i]);}vis[x]=false;}
}
int main()
{scanf("%d%d",&n,&m);int s,t,v,w,i;for (i=1;i<=m;++i){scanf("%d%d%d%d",&s,&t,&v,&w);insert(s,t,v);insert(t,s,w);}ans=2147483647;for (int i=1;i<=n;i<<=1){spfa(i,i);spfa(i,0);}if(ans==2147483647) ans=-1;printf("%d\n",ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！