首页 > 代码库 > 计蒜之道复赛 B D F

计蒜之道复赛 B D F

2024-10-04 05:46:02   211人阅读

B题是一个简单的模拟

求一下两个点中间在上deta的整数点

然后更新一下每个点的最后一次经过就好了

 

 1 #include<bits/stdc++.h> 2 #define cl(a,b) memset(a,b,sizeof(a)) 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 4 using namespace std; 5  6 const int maxn=300+10; 7  8 int gcd(int a,int b){return a?gcd(b%a,a):b;} 9 int abs(int a){if(a>0)return a;return -a;}10 11 int a[maxn][maxn];12 13 int main()14 {15     int n,m;16     scanf("%d%d",&n,&m);17     cl(a,0);18     for(int i=1;i<=n;i++)19     {20         int x1,y1,x2,y2,dx,dy;21         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);22         dx=x2-x1;23         dy=y2-y1;24         int k=gcd(abs(dx),abs(dy));25         dx/=k,dy/=k;26         x2+=dx;27         while(x1!=x2)28         {29 //            debug(x1),debug(y1);30             a[x1][y1]=i;31             x1+=dx,y1+=dy;32         }33     }34     int q;35     scanf("%d",&q);36     while(q--)37     {38         int x,y;39         scanf("%d%d",&x,&y);40         printf("%d\n",a[x][y]);41     }42     return 0;43 }/*44 45 5 846 2 5 5 247 5 2 3 848 8 4 1 449 2 2 5 850 8 7 4 151 452 3 453 5 254 6 455 3 556 57 */

 

D是一个最短路

需要注意的是每个城市群需要加两个点u‘和u‘‘

每个群内的城市连自己的城市群是

u‘->v

v->u‘‘

然后每个城市群之间

u‘->v‘‘

v‘->u‘‘

直接跑一遍spfa就行

需要注意的是：

1.n和m没有规定谁大谁小 所以加点的时候n*2+i和n+i是会冲突的

2.因为最大的值是2e5*2e6>2^31-1 所以ans要用ll存

3.由于上一点的存在 inf也要改……

 

  1 #include<bits/stdc++.h>  2 #define cl(a,b) memset(a,b,sizeof(a))  3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl  4 using namespace std;  5 typedef long long ll;  6   7 const int MAXN=4e5+10;  8 const ll INF=2e12;  9  10 struct Edge 11 { 12     int v; 13     int cost; 14     Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {} 15 }; 16  17 vector<Edge>E[MAXN]; 18  19 void addedge(int u,int v,int w) 20 { 21     E[u].push_back(Edge(v,w)); 22 } 23  24 bool vis[MAXN]; 25 int cnt[MAXN]; 26 ll dist[MAXN]; 27 int n,m; 28 int start,over; 29  30 ll SPFA(int start,int n) 31 { 32     for(int i=0;i<n+m*2+10;i++) 33     { 34         dist[i]=INF; 35         vis[i]=false; 36     } 37     vis[start]=true; 38     dist[start]=0; 39     queue<int>que; 40     while(!que.empty())que.pop(); 41     que.push(start); 42     memset(cnt,0,sizeof(cnt)); 43     cnt[start]=1; 44     while(!que.empty()) 45     { 46         int u=que.front(); 47         que.pop(); 48         vis[u]=false; 49         for(int i=0; i<E[u].size(); i++) 50         { 51             int v=E[u][i].v; 52             if(dist[v]>dist[u]+E[u][i].cost) 53             { 54                 dist[v]=dist[u]+E[u][i].cost; 55                 if(!vis[v]) 56                 { 57                     vis[v]=true; 58                     que.push(v); 59                     if(++cnt[v]>n) return -1; 60                 } 61             } 62         } 63     } 64     return dist[over]; 65 } 66  67 int main() 68 { 69     scanf("%d%d",&n,&m); 70     for(int i=1;i<=m;i++) 71     { 72         int k; 73         scanf("%d",&k); 74         for(int j=0;j<k;j++) 75         { 76             int x; 77             scanf("%d",&x); 78             addedge(x,n+m+i,0); 79             addedge(n+i,x,0); 80         } 81     } 82     int m1; 83     scanf("%d",&m1); 84     for(int i=0;i<m1;i++) 85     { 86         int u,v,w; 87         scanf("%d%d%d",&u,&v,&w); 88         addedge(u,v,w); 89         addedge(v,u,w); 90     } 91     int m2; 92     scanf("%d",&m2); 93     for(int i=0;i<m2;i++) 94     { 95         int u,v,w; 96         scanf("%d%d%d",&u,&v,&w); 97         addedge(n+m+u,n+v,w); 98         addedge(n+m+v,n+u,w); 99     }100     scanf("%d%d",&start,&over);101     ll ans=SPFA(start,n);102     printf("%lld\n",ans>=INF?-1:ans);103     return 0;104 }/*105 106 5 4107 2 5 1108 2 2 4109 1 3110 2 3 4111 2112 1 2 9113 1 5 18114 2115 1 2 6116 1 3 10117 1 5118 119 */

 

F是一个状压dp

（虽然没有16这么性感的数字 但是18也很明显了~

第一维表示当前状态 01表示是否删除

第二维表示已经删除的步数

用l r来枚举区间

数据范围不是很大(2^n)*n*n是可以容忍的

（也是调了好久啊……

 

 1 #include<bits/stdc++.h> 2 #define cl(a,b) memset(a,b,sizeof(a)) 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 4 using namespace std; 5 typedef long long ll; 6  7 const int maxn=20; 8 const int mod=1000000007; 9 10 int gcd(int a,int b)11 {12     return a?gcd(b%a,a):b;13 }14 15 bool check(int x,int y)16 {17     return x&(1<<y);18 }19 20 int n,k;21 int a[maxn];22 int dp[(1<<maxn)][maxn];23 24 void solve()25 {26     for(int i=0; i<(1<<n); i++)27     {28         for(int l=0; l<n; l++)29         {30             int tmp=i;31             if(check(i,l))32             {33                 int tmp1=a[l];34                 for(int r=l; r<n; r++)35                 {36                     if(check(i,r))37                     {38                         tmp^=(1<<r);39                         tmp1=gcd(tmp1,a[r]);40                         if(tmp1<k) break;41                         for(int j=1; j<=n; j++)42                         {43                             dp[i][j]=(dp[i][j]+dp[tmp][j-1])%mod;44                         }45                     }46                 }47             }48         }49     }50 }51 52 int main()53 {54     scanf("%d%d",&n,&k);55     cl(a,0),cl(dp,0);56     for(int i=0; i<n; i++)57     {58         scanf("%d",&a[i]);59     }60     dp[0][0]=1;61     solve();62     ll ans=0;63     for(int i=1; i<=n; i++)64     {65         ans+=1ll*i*dp[(1<<n)-1][i];66         ans%=mod;67     }68     printf("%lld\n",ans);69     return 0;70 }/*71 72 4 173 1 1 1 174 75 */

 

计蒜之道复赛 B D F


联系
我们