辣些数据结构的思维题（思维题好难一个都不会TAT）

洛谷P1268 树的重量

我觉得难点在于把每个叶子节点想象成分出来的叉
然后如果c是a--b这条边上分出来的，可以通过Dab,Dca,Dcb算出分叉边的长度，
长度=(Dac+Dbc-Dab)/2
怎么看c到底是哪两条边分叉出来的呢？
取最小的（洛谷后面的题解可以看懂）

代码：（只有一个测试数据感觉都不知道自己写的到底对不对

 1 #include <bits/stdc++.h>
 2 #define inf 1e9
 3 
 4 using namespace std;
 5 int n;  //n<=30
 6 int d[50][50];
 7 
 8 inline int f(int a,int b,int c){  //c是ab分叉，算叉出去那一段长度
 9     return (d[a][c]+d[b][c]-d[a][b])/2;
10 }
11 
12 int main(){
13     //freopen("owo.in","r",stdin);
14     while(scanf("%d",&n)==1&&n){
15         memset(d,0,sizeof(d));
16         for (int i=1; i<n; i++) for (int j=i+1; j<=n; j++) { scanf("%d",&d[i][j]); d[j][i]=d[i][j]; }
17         int ans=d[1][2];
18         for (int i=3; i<=n; i++) {  //把每个点作为分叉加进来
19             int ta=inf;
20             for (int j=1; j<=i; j++) for (int k=1; k<=i; k++) if(k!=i&&j!=i&&j!=k) ta=min(ta, f(j,k,i) );
21             ans+=ta;
22         }
23         printf("%d
",ans);
24     }
25     return 0;
26 }

( ͡° ͜ʖ ͡°)

洛谷P2375 [NOI2014]动物园

题意：构造一个num数组一一对于字符串

 1 #include <bits/stdc++.h>
 2 #define nmax 1000010
 3 #define mod 1000000007
 4 
 5 using namespace std;
 6 typedef long long ll;
 7 char b[nmax];
 8 int num[nmax],ne[nmax],ta[nmax],jump[nmax];
 9 int l;
10 ll ans;
11 
12 void init(){
13     ans=1;
14     memset(num,0,sizeof(num));
15     memset(ne,0,sizeof(ne));
16     memset(ta,0,sizeof(ta));
17     memset(jump,0,sizeof(jump));
18 }
19 
20 void build(){
21     for (int i=2; i<=l; i++) {
22         int j=ne[i-1];
23         while( b[j+1]!=b[i] && j ) j=ne[j];
24         if(b[j+1]==b[i]) ne[i]=j+1;
25     }
26 }
27 
28 void b2(){ //它第一个不重叠的公共前后缀的位置
29     for (int i=2; i<=l; i++) {
30         int p=jump[i-1];
31         if( b[p+1] == b[i] && (p+1)<=(i/2) ) jump[i]=p+1;
32         else {
33             while ( p && ( (p+1)>(i/2) || b[p+1]!=b[i] ) )  p=ne[p];
34             if(b[p+1]==b[i]) jump[i]=p+1;
35         }
36     }
37 }
38 
39 void solve(){
40     int tmp;
41     for (int i=2; i<=l; i++) {
42         int j=ne[i],pd=i/2;
43         if(j) ta[i]=ta[j]+1;
44         if( jump[i] ) tmp=ta[jump[i]]+1; else tmp=0;
45         ans*=(tmp+1);
46         ans%=mod;
47     }
48 }
49 
50 int main(){
51     int t;
52     cin>>t;
53     while(t--){
54         init();
55         scanf("%s",b+1);
56         l=strlen(b+1);
57         build();
58         b2();
59         solve();
60         printf("%lld
",ans);
61     }
62     return 0;
63 }

^3^

CF Round #581 (Div. 2)

这道题。。。它给的p1,....,pn里面假设连续三个点 pk,p(k+1),p(k+2) 容易知道如果pk到p（k+2）的最短路是2的话p(k+1)是可以删去的
于是愉快的扫一遍每次这样看三个。
然后就wa6了
wa的原因：这里如果pk已经被删去了，是要影响到p(k+1)的。
比如p1,p2,p3,p4，如果p2被删，p4,p2的最短路是2，会删3，但是如果p1p4的最短路是2.。。就删错了
正确姿势：假设前面已经得到一连串p1~pk,现在最后得到的pk，然后往后面走，走到pj，如果p(j+1)和pk的距离和j+1-k相等的话，就可以把pj删了

代码：

 1 #include <bits/stdc++.h>
 2 #define inf 1e6
 3 #define mmax 5000010
 4 
 5 using namespace std;
 6 int n,m,ans=0,idx=0;
 7 int e[200][200];
 8 int p[mmax],del[mmax]={0};
 9 char in[200];
10 
11 void floyd(){
12     for(int k=1;k<=n;k++)  for(int i=1;i<=n;i++)  for(int j=1;j<=n;j++)
13         if(e[i][j]>e[i][k]+e[k][j] )   e[i][j]=e[i][k]+e[k][j];
14 }
15 
16 int main(){
17     cin>>n;
18     for (int i=1; i<=n; i++) {
19         scanf("%s",in+1);
20         for (int j=1; j<=n; j++) if(in[j]=='1') e[i][j]=1; else e[i][j]=inf;
21     }
22     floyd();
23     for (int i=1; i<=n; i++) e[i][i]=0;
24     cin>>m;
25     scanf("%d%d",&p[0],&p[1]);
26     if(m==2){
27         printf("2
");
28         printf("%d %d
",p[0],p[1]);
29     }else{
30         for (int i=2; i<m; i++) {
31             scanf("%d",&p[i]);
32             if( e[ p[idx] ][ p[i] ]>=i-idx ) {
33                     ans++;
34                     del[i-1]=1;
35             }else idx=i-1;
36         }
37 
38         printf("%d
",m-ans);
39         for (int i=0; i<m; i++) if(!del[i]) printf("%d ",p[i]);
40         cout<<endl;
41     }
42     return 0;
43 }

嘤雄不朽+1s

UVALive - 3902

vjudge上的地址 https://vjudge.net/problem/UVALive-3902
容易想到的贪心，就是对于每个叶子节点，把服务器的复制放在尽量离他远的地方。
但是就算是用了上面一种贪心策略还是会有很多种放置♂方式
然后又贪心，从深度♂比较大的客户端开始考虑

代码：

 1 #include <bits/stdc++.h>
 2 #define nmax 1100
 3 
 4 using namespace std;
 5 int cas,k,n,ina,inb,s;
 6 vector <int> g[nmax];
 7 int vis[nmax]={0},fa[nmax]={0};
 8 struct node{
 9     int d,u;
10     bool operator < (const node a){ return a.d<d; }
11 }x[nmax];
12 
13 void dfs1(int u){ //以s为根拉树，然后处理出每个点的父亲
14     for (int i=0; i<g[u].size(); i++) {
15         int v=g[u][i];
16         if(fa[v]==0) { fa[v]=u; x[v].d=x[u].d+1; dfs1(v); }
17     }
18 }
19 
20 void dfs(int f,int u,int dep){  //给某个服务器服务到的点标1
21     vis[u]=1;
22     if(dep==k) return;
23     for (int i=0; i<g[u].size(); i++) if(g[u][i]!=f) dfs(u,g[u][i],dep+1);
24 }
25 
26 int main(){
27     cin>>cas;
28     while(cas--){
29         memset(vis,0,sizeof(vis));
30         memset(fa,0,sizeof(fa));
31         scanf("%d%d%d",&n,&s,&k);
32         x[s].d=0;
33         for (int i=1; i<=n; i++) { x[i].u=i; g[i].clear(); }
34         for (int i=1; i<n; i++) {
35             scanf("%d%d",&ina,&inb);
36             g[ina].push_back(inb);
37             g[inb].push_back(ina);
38         }
39         fa[s]=s;
40         dfs1(s);
41         sort(x+1,x+n+1);
42         dfs(s,s,0);
43         int ans=0;
44         for (int i=1; i<=n; i++) {
45             int u=x[i].u;
46             if( g[u].size()>1 || vis[u] ) continue;
47             int v=u;
48             for (int i=0; i<k; i++) v=fa[v];
49             dfs(v,v,0);
50             ans++;
51         }
52         printf("%d
",ans);
53     }
54     return 0;
55 }

嘤年早逝