首页 > 代码库 > 20140710总结

20140710总结

2024-07-11 14:15:00   219人阅读

　　今天第一题很水，主要坑在负数上，不多说，上代码。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 long long N,K; 6 long long a[1000000]; 7 long long flags[1000000]; 8 int main() 9 {10     scanf("%I64d%I64d",&N,&K);11     memset(a,0,sizeof(a));12     memset(flags,0,sizeof(flags));13     for(int i=1;i<=N;i++)14     {15         scanf("%I64d",&a[i]);16         a[i]=(a[i]+a[i-1])%K;17         while(a[i]<0)18             a[i]+=K;19         a[i]%=K;20     }21     for(int i=0;i<=N;i++)22         flags[a[i]%K]++;23     long long ans=0;24     for(int i=0;i<K;i++)25         ans+=max(0LL,flags[i]*(flags[i]-1)/2);26     printf("%I64d\n",ans);27 }
View Code

　　今天第二题，二分答案+spfa找负环。思路很清晰，大意就是因为直接找简单回路要记录有哪些点走了，走了那些边。于是考虑二分答案，判合法，判的方法是：减掉答案，如果存在一条回路使答案<=0，那么答案一定合法。这让人想到了负环（其实是非正环）。做法是spfa，如果dis[to]>=dis[now]+len; (注意“=”很重要)能一直更新（更新了点数次以上），那么说明有负环。

　　我当场之所以WA40，后来查错，才发现是INF开小了！！！！！洗内！！！！！！

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 struct JackSlowFuck 7 { 8     int from,to,len,next; 9 }Fu[1010];10 int node[610];11 int now;12 double dis[610];13 bool in[610];14 int N,M,f,t,l;15 int cs[610];16 void addedge(int f,int t,int l)17 {18     Fu[++now].next=node[f];19     node[f]=now;20     Fu[now].to=t;21     Fu[now].len=l;22 }23 bool spfa(int s,double ch)24 {25     for(int i=1;i<=N;i++)26         dis[i]=100000000.0;27     memset(cs,0,sizeof(cs));28     memset(in,0,sizeof(in));29     dis[s]=0.0;30     queue <int> Q;31     Q.push(s);32     while(!Q.empty())33     {34         int nn=Q.front();35         Q.pop();36         cs[nn]++;37         if(cs[nn]>N+10)38             return true;39         in[nn]=false;40         for(int k=node[nn];k;k=Fu[k].next)41         {42             if(dis[Fu[k].to]>=dis[nn]+Fu[k].len-ch)43             {44                 dis[Fu[k].to]=dis[nn]+Fu[k].len-ch;45                 if(!in[Fu[k].to])46                 {47                     in[Fu[k].to]=true;48                     Q.push(Fu[k].to);49                 }50             }51         }52     }53     return false;54 }55 int main()56 {57     scanf("%d%d",&N,&M);58     for(int i=1;i<=M;i++)59     {60         scanf("%d%d%d",&f,&t,&l);61         addedge(f,t,l);62     }63     double l=0.0,r=10000000.0;64     while(r-l>0.00001)65     {66         double mid=(l+r)/2;67         if(spfa(1,mid))68             r=mid;69         else70             l=mid;71     }72     printf("%.2lf\n",r);73 }
View Code

　　第三题不会。


联系
我们