今天第一题很水，主要坑在负数上，不多说，上代码。
1 #include2 #include 3 #include 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
今天第二题，二分答案+spfa找负环。思路很清晰，大意就是因为直接找简单回路要记录有哪些点走了，走了那些边。于是考虑二分答案，判合法，判的方法是：减掉答案，如果存在一条回路使答案<=0，那么答案一定合法。这让人想到了负环（其实是非正环）。做法是spfa，如果dis[to]>=dis[now]+len; (注意“=”很重要)能一直更新（更新了点数次以上），那么说明有负环。
我当场之所以WA40，后来查错，才发现是INF开小了！！！！！洗内！！！！！！
1 #include2 #include 3 #include 4 #include 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 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 }
第三题不会。