A.meeting（树的直径）
•题意
n给城市有n-1条路相连，
每两个城市之间的道路花费为1
有k个人在k个城市，
问这k个人聚集在同一个城市的最小花费
•思路
•代码
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e5+5; 4 vector<int> g[maxn]; 5 bool vis[maxn]; 6 int ans; 7 int farx; 8 9 void dfs(int u,int pre,int len) 10 { 11 if(vis[u]) 12 { 13 if(len>ans) 14 { 15 ans=len; 16 farx=u; 17 } 18 } 19 for(int i=0;i<g[u].size();i++) 20 { 21 int v=g[u][i]; 22 if(v!=pre) 23 dfs(v,u,len+1); 24 } 25 } 26 int main() 27 { 28 int n,k; 29 cin>>n>>k; 30 int x,y; 31 for(int i=1;i<=n-1;i++) 32 { 33 cin>>x>>y; 34 g[x].push_back(y); 35 g[y].push_back(x); 36 } 37 for(int i=1;i<=k;i++) 38 { 39 cin>>x; 40 vis[x]=1; 41 } 42 ans=1; 43 //因为没有0城市，我们可以把它当作前一个城市 44 //最远的两个点都是从0城市出发 对结果没有影响 45 dfs(x,0,1); 46 dfs(farx,0,1); 47 cout<<ans/2<<endl; 48 }
D.triples I（构造）
•题意
给你一个数 a，x | y = a 的 x,y;
其中x%3==0,y%3==0
•思路
我在进行十进制和二进制转化时，发现了一个特别神奇的现象
从20开始到28为例
256 128 64 32 16 8 4 2 1
奇数位的数21,23,25,27 %3 =2
偶数位的数20,22,24,28 %3 =1
那我们要找 x|y=a 就可以在此基础上进行操作了！
分别记录一下a中二进制奇数位和偶数位中1的个数,记为w[1]和w[0]
然后分情况讨论
1）a%3=0时，a可以直接输出
2）a%3=1时
①w[1]>=2时，因为奇数位%3=1,可以让a-奇数位上的一个数f[奇][1]，x=(a-f[奇][1])，y=(a-f[奇][2]) x%3=0,y%3=0;
②w[1]==1时，只有一个奇数位，那么可以让 x=(a-f[奇][1]) ,因为偶数位%3=2，两个%3=2的相加 (f[偶][1]+f[偶][2])%3=4%3=1，y=(a-f[偶][1]-f[偶][2])
③w[1]==0时，没有奇数位全是偶数位，设有x个偶数位，x*2%3=1,则x为5的倍数。与②中的y同理，x=(a-f[偶][1]-f[偶][2])，y=(a-f[偶][3]-f[偶][4])
3）a%3=2时，与2)同理
注：
上述 '-' 换成 '^' 也可以，原理就是把某个位置上的1消去
•代码
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 int main() 5 { 6 int t; 7 scanf("%d",&t); 8 while(t--) 9 { 10 ll f[2][62];//f[0][i]代表偶数位(1<<i)的值，f[1][i]代表奇数位(1<<i)的值 11 ll w[2]={0,0}; //偶数位、奇数位 上的1的个数 12 ll a; 13 scanf("%lld",&a); 14 if(a%3==0) 15 printf("1 %lld ",a); 16 else 17 { 18 int m=(a%3)/2; //余数为1,2 除以2 得0,1 便于和f[][]对应计算 19 // cout<<"m:"<<m<<endl; 20 ll n=a; 21 for(int i=0;n;i++) 22 { 23 if(n&1) 24 { 25 w[i&1]++; 26 f[i&1][w[i&1]]=(1ll<<i); 27 // printf("f[%d][%lld]:%lld ",i&1,w[i&1],f[i&1][w[i&1]]); 28 } 29 n>>=1; 30 } 31 printf("2 "); 32 if(w[m]>=2) 33 printf("%lld %lld ",a^f[m][1],a^f[m][2]); 34 else if(w[m]==1) 35 printf("%lld %lld ",a^f[m][1],a^f[!m][1]^f[!m][2]); 36 else if(w[m]==0) 37 printf("%lld %lld ",a^f[!m][1]^f[!m][2],a^f[!m][3]^f[!m][4]); 38 } 39 } 40 }
J.free（图论 分层图最短路）
•题意
给你n个城市,n-1条道路
经过每一条要花费这条路的代价
现给你k个机会，使得最多k条路的代价为0
问从起点s到终点t,花费最少的代价
•思路
分层图最短路经典裸题
•代码
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 1005 4 #define M 2005 5 #define lowbit(x) x&(-x) 6 #define ll long long 7 const ll inf =9e18; 8 int head[N],n,m,k,cnt; 9 ll dp[N][N]; 10 int s,t; 11 struct Edge 12 { 13 int from,to,nex; 14 ll w; 15 }e[M*2]; 16 struct Node 17 { 18 int a,b; //a:终点 b:已经用了几次免费路 19 ll dis; //起点到a的当前最短距离 20 bool operator <(const Node &p)const 21 { 22 return dis>p.dis; 23 } 24 }; 25 void init() 26 { 27 for(int i=0;i<=n;i++) 28 { 29 head[i]=-1; 30 } 31 cnt=0; 32 } 33 void add(int u,int v,ll val) 34 { 35 e[cnt].from=u; 36 e[cnt].to=v; 37 e[cnt].nex=head[u]; 38 e[cnt].w=val; 39 head[u]=cnt++; 40 } 41 void bfs() 42 { 43 for(int i=0;i<=n;i++) 44 { 45 for(int j=0;j<=15;j++) 46 { 47 dp[i][j]=inf; 48 } 49 } 50 dp[s][0]=0; //dp[i][j] :从起点s到i ，已经有j次免费的路的最短路径 51 priority_queue<Node>que; 52 que.push(Node{s,0,0}); 53 while(!que.empty()) 54 { 55 Node tmp=que.top(); 56 que.pop(); 57 int u=tmp.a; 58 int b=tmp.b; 59 for(int i=head[u];i!=-1;i=e[i].nex) 60 { 61 int v=e[i].to; 62 if(dp[v][b]>tmp.dis+e[i].w)//这条路不当作免费路 63 { 64 dp[v][b]=tmp.dis+e[i].w; 65 que.push(Node{v,b,dp[v][b]}); 66 } 67 if(b+1<=k) 68 { 69 if(dp[v][b+1]>tmp.dis)//这条路当作免费路 70 { 71 dp[v][b+1]=tmp.dis; 72 que.push(Node{v,b+1,tmp.dis}); 73 } 74 } 75 } 76 } 77 } 78 int main() 79 { 80 scanf("%d%d%d%d%d",&n,&m,&s,&t,&k); 81 init(); 82 int u,v; 83 ll w; 84 for(int i=0;i<m;i++) 85 { 86 scanf("%d%d%lld",&u,&v,&w); 87 add(u,v,w); 88 add(v,u,w); 89 } 90 bfs(); 91 printf("%lld ",dp[t][k]); 92 return 0; 93 }
K.number（思维）
•题意
给你一个 串s，s 由 '0'~'9' 的数字组成；
求能整除 300 的不同的子串的个数；
对于相同内容的子串，如果含有位置不同的字符，当作不同子串处理；
并且可以有前导0；
•题解
首先看300的倍数，也就是3的倍数后面加两个0，
3的倍数的特点是各位数之和是3的倍数，那后面再加两个0就是300的倍数
对于3来讲，各个数mod3结果为0,1,2
既然这样，那我们来看前缀和，
如果在(l,r]区间里增量为3 的倍数，也就是在(l,r]区间里前缀和mod3结果相同
那肯定是3的倍数了，后面再加00就是300的倍数
注意：
一个0也是3的倍数，遇到0，ans就要+1
•代码
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 1005 4 #define M 2005 5 #define ll long long 6 const ll inf =9e18; 7 int head[N],n,m,k,cnt; 8 ll dp[N][N]; 9 int s,t; 10 struct Edge 11 { 12 int from,to,nex; 13 ll w; 14 }e[M*2]; 15 struct Node 16 { 17 int a,b; //a:终点 b:已经用了几次免费路 18 ll dis; //起点到a的当前最短距离 19 bool operator <(const Node &p)const 20 { 21 return dis>p.dis; 22 } 23 }; 24 void init() 25 { 26 for(int i=0;i<=n;i++) 27 head[i]=-1; 28 cnt=0; 29 } 30 void add(int u,int v,ll val) 31 { 32 e[cnt].from=u; 33 e[cnt].to=v; 34 e[cnt].nex=head[u]; 35 e[cnt].w=val; 36 head[u]=cnt++; 37 } 38 void bfs() 39 { 40 for(int i=0;i<=n;i++) 41 for(int j=0;j<=k;j++) 42 dp[i][j]=inf; 43 dp[s][0]=0; //dp[i][j] :从起点s到i ，已经有j次免费的路的最短路径 44 priority_queue<Node>que; 45 que.push(Node{s,0,0}); 46 while(!que.empty()) 47 { 48 Node tmp=que.top(); 49 que.pop(); 50 int u=tmp.a; 51 int b=tmp.b; 52 for(int i=head[u];i!=-1;i=e[i].nex) 53 { 54 int v=e[i].to; 55 if(dp[v][b]>tmp.dis+e[i].w)//这条路不当作免费路 56 { 57 dp[v][b]=tmp.dis+e[i].w; 58 que.push(Node{v,b,dp[v][b]}); 59 } 60 if(b+1<=k) 61 { 62 if(dp[v][b+1]>tmp.dis)//这条路当作免费路 63 { 64 dp[v][b+1]=tmp.dis; 65 que.push(Node{v,b+1,tmp.dis}); 66 } 67 } 68 } 69 } 70 } 71 int main() 72 { 73 scanf("%d%d%d%d%d",&n,&m,&s,&t,&k); 74 init(); 75 int u,v; 76 ll w; 77 for(int i=0;i<m;i++) 78 { 79 scanf("%d%d%lld",&u,&v,&w); 80 add(u,v,w); 81 add(v,u,w); 82 } 83 bfs(); 84 printf("%lld ",dp[t][k]); 85 return 0; 86 }