首页 > 代码库 > Codeforces Round #284 (Div. 1)

Codeforces Round #284 (Div. 1)

A. Crazy Town

  这一题只需要考虑是否经过所给的线,如果起点和终点都在其中一条线的一侧,那么很明显从起点走点终点是不需要穿过这条线的,否则则一定要经过这条线,并且步数+1。用叉积判断即可。

 

代码:

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<string> 5 #include<map> 6 #define N 100010 7 #define M 1010 8 using namespace std; 9 int x1,y1,x2,y2,a,b,c,i,ans,n;10 double x,y,xx,yy;11 double cross(double x1,double y1,double x2,double y2,double x3,double y3)12 {13     return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);14 }15 int main()16 {17     scanf("%d%d",&x1,&y1);18     scanf("%d%d",&x2,&y2);19     scanf("%d",&n);         20     for (i=1;i<=n;i++)21     {22         scanf("%d%d%d",&a,&b,&c);23         if (b)24         {25         x=1;26         y=(-c-a)*1.0/b;27         xx=3;28         yy=(-c-3*a)*1.0/b;29         }30         else31         {32         y=1;33         x=(-c-b)*1.0/a;34         yy=3;35         xx=(-c-3*b)*1.0/a;36         }37         if (cross(x,y,xx,yy,x1,y1)*cross(x,y,xx,yy,x2,y2)<0)38         ans++;39     }40     printf("%d",ans);41 }

 

C. Array and Operations

  要使操作数目最多首先每个操作肯定是要除以一个质数的,因为一个合数可以拆成多个质数,那么操作数目明显会增加。对于每个质数可以独立考虑,对于一个质数x,假设a[i]中有sum[i]个x,一次操作会使一个数对同时减少一个x,现在要考虑的就是如何操作使得操作次数最多,由于题目保证数对的和是奇数,也就是一个数对分别有一个奇数和一个偶数,那么就可以建二分图跑网络流,对于一个数对,假设L[i]是奇数,R[i]是偶数,那么从源点s连一条流量为sum[L[i]]的边到L[i],L[i]连一条流量无穷大的边到R[i],R[i]连一条流量为sum[R[i]]的边到汇点t。跑出来的最大流就是对于质数x的最大操作数,对于每个质数的操作数累加起来就是答案。

 

代码

  1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #include<string>  5 #include<map>  6 #define N 100010  7 #define M 810  8 #define INF 0x37373737  9 using namespace std; 10 int dp,pre[M],p[M],tt[M],g[M],vis[M],dis[M],z[N],now[M],s,t,a[N],sum[N]; 11 int n,m,i,L[N],R[N],flag,j,ans; 12 void link(int x,int y,int z) 13 { 14     dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y;g[dp]=z; 15     dp++;pre[dp]=p[y];p[y]=dp;tt[dp]=x;g[dp]=0; 16 } 17 int min(int a,int b) 18 { 19     if (a<b) return a;return b; 20 } 21 int bfs() 22 { 23     int i,head,tail; 24     memcpy(now,p,sizeof(p)); 25     memset(vis,0,sizeof(vis)); 26     head=0;tail=1; 27     vis[s]=1; 28     dis[s]=0; 29     z[tail]=s; 30     do 31     { 32         head++; 33         i=p[z[head]]; 34         while (i) 35         { 36             if ((vis[tt[i]]==0)&&(g[i]>0)) 37             { 38                 vis[tt[i]]=1; 39                 dis[tt[i]]=dis[z[head]]+1; 40                 tail++;z[tail]=tt[i]; 41             } 42             i=pre[i]; 43         } 44     } 45     while (head!=tail); 46     return vis[t]; 47 } 48 int dfs(int u,int flow) 49 { 50     int ans,tmp,i; 51     if (u==t) return flow; 52     i=now[u]; 53     ans=0; 54     while (i) 55     { 56         if ((dis[u]+1==dis[tt[i]])&&(g[i]>0)) 57         { 58             tmp=dfs(tt[i],min(flow-ans,g[i])); 59             ans+=tmp;g[i]-=tmp; 60             if (i%2==1) g[i+1]+=tmp;else g[i-1]+=tmp; 61             if (flow==ans) return flow; 62         } 63         i=pre[i]; 64         now[u]=i; 65     } 66     if (flow>ans) dis[u]=1; 67     return ans; 68 } 69 int main() 70 { 71     scanf("%d%d",&n,&m); 72     for (i=1;i<=n;i++) 73     scanf("%d",&a[i]); 74     for (i=1;i<=m;i++) 75     scanf("%d%d",&L[i],&R[i]); 76     for (i=2;i<=35000;i++) 77     { 78         flag=0; 79         for (j=1;j<=n;j++) 80         if (a[j]%i==0) 81         { 82             flag=1; 83             while (a[j]%i==0) 84             { 85                 sum[j]++;a[j]=a[j]/i; 86             } 87         } 88     //---------------------------- 89         if (flag) 90         { 91             dp=0; 92             memset(p,0,sizeof(p)); 93             s=0;t=n+1; 94             for (j=1;j<=n;j++) 95             if (j%2==0) 96             link(j,t,sum[j]); 97             else 98             link(s,j,sum[j]); 99             for (j=1;j<=m;j++)100             if (L[j]%2==0)101             link(R[j],L[j],INF);102             else103             link(L[j],R[j],INF);104             while (bfs()) ans=ans+dfs(s,INF);105             for (j=1;j<=n;j++)106             sum[j]=0;107         }108         flag=0;109     }110     for (i=1;i<=n;i++)111     if (a[i]>1)112     {113         flag=a[i];114         for (j=1;j<=n;j++)115             while (a[j]%flag==0)116             {117                 sum[j]++;a[j]=a[j]/flag;118             }119         dp=0;120             memset(p,0,sizeof(p));121             s=0;t=n+1;122             for (j=1;j<=n;j++)123             if (j%2==0)124             link(j,t,sum[j]);125             else126             link(s,j,sum[j]);127             for (j=1;j<=m;j++)128             if (L[j]%2==0)129             link(R[j],L[j],INF);130             else131             link(L[j],R[j],INF);132             while (bfs()) ans=ans+dfs(s,INF);133             for (j=1;j<=n;j++)134             sum[j]=0;135     }136     printf("%d",ans);137 }

D. Traffic Jams in the Land

  正解是线段树,由于a[i]的值只可能是2到6,假设当前到了节点i,用了时间time,那么对于当前是要花费1s时间经过还是2s时间经过,用time和time%lcm(2,3,4,5,6)判断是没有差别的,那么对于线段树的每个节点都开60个数组,分别表示在(time&60)的时间进入该节点所表示的线段,并用了多少时间走出去,这样就可以对线段树进行修改和查询了。下面贴出的代码是用分块做的,块内元素固定为40,思想是和线段树一样的,只是每次修改都对所在的块暴力维护,也能卡过所有的数据。。。。

 

代码

 1 #include<cstdio> 2 #include<cstring> 3 #define N 100100 4 #define Q 40 5 int n,i,j,a[N],s[30000][60],q,x,y,bx,by,tmp; 6 char ch; 7 int min(int a,int b) 8 { 9     if (a<b) return a;return b;10 }11 void change(int x)12 {13     int i,j,tmp;14     for (j=0;j<=59;j++)15     {16         tmp=j;17         for (i=(x-1)*Q+1;i<=min(x*Q,n);i++)18         {19             if (tmp%a[i]==0) tmp++;20             tmp++;21         }22         s[x][j]=tmp-j;23     }24 }25 int query(int x,int y,int bx,int by)26 {27     int i,tmp;28     tmp=0;29     for (i=x;i<=bx*Q;i++)30     {31         if (tmp%a[i]==0) tmp++;32         tmp++;33     }34     for (i=bx+1;i<=by-1;i++)35     tmp=tmp+s[i][tmp%60];36     for (i=(by-1)*Q+1;i<=y;i++)37     {38         if (tmp%a[i]==0) tmp++;39         tmp++;40     }41     return tmp;42 }43 int main()44 {45     scanf("%d",&n);46     for (i=1;i<=n;i++)47     scanf("%d",&a[i]);48     for (i=1;i<=(n-1)/Q+1;i++)49     change(i);50     scanf("%d",&q);51     for (i=1;i<=q;i++)52     {53         getchar();54         scanf("%c%d%d",&ch,&x,&y);55         if (ch==C)56         {57             a[x]=y;58             change((x-1)/Q+1);59         }60         else61         {62             y--;63             bx=(x-1)/Q+1;64             by=(y-1)/Q+1;65             if (bx==by)66             {67                 tmp=0;68                 for (j=x;j<=y;j++)69                 {70                     if (tmp%a[j]==0) tmp++;71                     tmp++;72                 }73                 printf("%d\n",tmp);74             }75             else76             {77                 printf("%d\n",query(x,y,bx,by));78             }79         }80     }81 }

 

Codeforces Round #284 (Div. 1)