第二届华北水利水电大学校赛

冷不防 2021-12-24 03:45 365阅读 0赞

***Xor and Sum*  **

之前做过一道异或的。感觉有点眼熟，发现不是。由于对异或一点也不熟悉。所以直接放弃了

首先写出来几项看看。

a:         1   2   4   1    1     2      4

prex :   1   3   7   6    7     5      1

prey:    1   3   7   8    9    11     15

可以发现如果区间异或和==区间和，那么缩小区间还是一样的。如果！=,那么扩大区间也是一样的。

所以可以枚举左端点，然后计算区间个数。

如果当前p和i满足，p++就是缩小区间，明显满足，所以可以省去，得出结果I-p。如果不满足，就找到一个满足点。当i=p，肯定满足。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=2e5+10;
     4 
     5 int prex[maxn],prey[maxn];
     6 
     7 int main() {
     8     int n;
     9     while(~scanf("%d",&n)) {
    10         for(int i=1;i<=n;i++) {
    11             int x;
    12             scanf("%d",&x);
    13             prex[i]=prex[i-1]^x;
    14             prey[i]=prey[i-1]+x;
    15         }
    16         int p=0;
    17         long long ans=0;
    18         for(int i=1;i<=n;i++) {
    19             while((prex[i]^prex[p])!=prey[i]-prey[p]) p++;
    20             ans+=i-p;
    21         }
    22         printf("%lld\n",ans);
    23     }
    24 }

**生命之树**

比赛的时候跑了每一个青蛙节点，然后求都能到达的。其实只需要求最远的两个即可。也就是包含青蛙的树的直径。然后看能同时到达这两个节点的节点有多少个。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=100010;
     4 
     5 int _,n,m,d,col[maxn],dis[maxn],newcol[maxn];
     6 vector<int> G[maxn];
     7 
     8 void dfs(int u,int p) {
     9     dis[u]=dis[p]+1;
    10     for(int i=0;i<G[u].size();i++) {
    11         int v=G[u][i];
    12         if(v!=p) dfs(v,u);
    13     }
    14 }
    15 
    16 int main() {
    17     for(scanf("%d",&_);_;_--) {
    18         scanf("%d%d%d",&n,&m,&d);
    19         for(int i=1;i<=n;i++) {
    20             G[i].clear();
    21             col[i]=0;
    22         }
    23         for(int i=0;i<m;i++) {
    24             int x;
    25             scanf("%d",&x);
    26             col[x]=1;
    27         }
    28         for(int i=1;i<n;i++) {
    29             int u,v;
    30             scanf("%d%d",&u,&v);
    31             G[u].push_back(v);
    32             G[v].push_back(u);
    33         }
    34         dis[0]=-1;
    35         dfs(1,0);
    36         int maxx,s,t;
    37         maxx=-1,s=-1;
    38         for(int i=1;i<=n;i++) {
    39             if(col[i]) {
    40                 if(dis[i]>maxx) {
    41                     maxx=dis[i];
    42                     s=i;
    43                 }
    44             }
    45         }
    46         dfs(s,0);
    47         maxx=-1;
    48         t=-1;
    49         for(int i=1;i<=n;i++) {
    50             if(col[i]) {
    51                 if(dis[i]>maxx) {
    52                     maxx=dis[i];
    53                     t=i;
    54                 }
    55             }
    56         }
    57         for(int i=1;i<=n;i++) col[i]=0;
    58         for(int i=1;i<=n;i++) {
    59             if(dis[i]<=d) col[i]=1;
    60         }
    61         dfs(t,0);
    62         int ans=0;
    63         for(int i=1;i<=n;i++) {
    64             if(dis[i]<=d&&col[i]) ans++;
    65         }
    66         printf("%d\n",ans);
    67     }
    68 }

DFS

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 typedef double db;
     5 typedef pair<int,int> pii;
     6 typedef vector<int> vi;
     7 #define de(x) cout << #x << "=" << x << endl
     8 #define rep(i,a,b) for(int i=a;i<b;++i)
     9 #define all(x) (x).begin(),(x).end()
    10 #define sz(x) (int)(x).size()
    11 #define mp make_pair
    12 #define pb push_back
    13 #define fi first
    14 #define se second
    15 
    16 const int N = 100005;
    17 int n, m, d;
    18 int h[N];
    19 vi g[N];
    20 int vis[N], dis[N];
    21 
    22 int bfs(int s, int f) {
    23     queue<int> Q;
    24     Q.push(s);
    25     vis[s]++;
    26     dis[s] = 0;
    27     while (!Q.empty()) {
    28         int u = Q.front(); Q.pop();
    29         for(int i = 0; i < sz(g[u]); i++) {
    30             int v = g[u][i];
    31             if (vis[v] == f) {
    32                 vis[v]++;
    33                 Q.push(v);
    34                 dis[v] = dis[u] + 1;
    35             }
    36         }
    37     }
    38     int Max = -1, ans;
    39     for (int i = 1; i <= n; i++) {
    40         if (h[i]) {
    41             if (Max < dis[i]) {
    42                 Max = dis[i];
    43                 ans = i;
    44             }
    45         }
    46     }
    47     return ans;
    48 }
    49 
    50 void solve() {
    51 
    52         scanf("%d%d%d", &n, &m, &d);
    53         for (int i = 1; i <= n; i++) h[i] = 0, g[i].clear(), vis[i] = 0;
    54         memset(h, 0, sizeof(h));
    55         while (m--) {
    56             int x; scanf("%d", &x);
    57             h[x] = 1;
    58         }
    59         for (int i = 1; i < n; i++) {
    60             int u, v; scanf("%d%d", &u, &v);
    61             g[u].pb(v);
    62             g[v].pb(u);
    63         }
    64         int s = bfs(1, 0);
    65         int t = bfs(s, 1);
    66         for(int i = 1; i <= n; i++) h[i] = 0;
    67         for(int i = 1; i <= n; i++) if (dis[i] <= d) h[i]++;
    68         bfs(t, 2);
    69         int ans = 0;
    70         for (int i = 1; i <= n; i++) if (dis[i] <= d && h[i]) ans++;
    71         printf("%d\n", ans);
    72 
    73 }
    74 
    75 int main() {
    76     int ti;
    77     scanf("%d", &ti);
    78     for (int i = 0; i < ti; i++) {
    79         solve();
    80     }
    81     return 0;
    82 }

BFS

**魔法扑克 **

分析可以发现花色是最主要的（算贪心？易证）。所以就可以找到出现花色最多的牌，但是不是这种花色的牌都满足，比如 2 3 8 9 10  显然最长合法的是8 9 10。因为2 和 3跟他们连不到一起。且 2 3长度为2，小于8 9 10长度为3。

还要处理 1的情况。当时傻逼了，以为1和13必须得同时出现。。。其实出现1就可以了。自闭。。。。改了就AC了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int inf=0x3f3f3f3f;
     4 
     5 int _;
     6 vector<int> t[10];
     7 //A12 A6 A5 A10 A1
     8 int main() {
     9     //freopen("in.txt", "r", stdin);
    10     //freopen("out.txt", "w", stdout);
    11     map<char,int> mp;
    12     mp['A']=1;
    13     mp['B']=2;
    14     mp['C']=3;
    15     mp['D']=4;
    16     for(scanf("%d",&_);_;_--) {
    17         string s;
    18         memset(t,0,sizeof(t));
    19         for(int i=0;i<5;i++) {
    20             cin>>s;
    21             int id=s[0]-'A'+1;
    22             int num=0,len=s.length();
    23             for(int i=1;i<len;i++) {
    24                 num=num*10+s[i]-'0';
    25             }
    26             t[id].push_back(num);
    27         }
    28         int ans=-1,maxx=-1;
    29         for(int i=1;i<=4;i++) {
    30             if(!t[i].size()) continue;
    31             int flag=0,len=t[i].size();
    32             for(int j=0;j<len;j++) {
    33                 if(t[i][j]==1) {
    34                     flag=1;
    35                     break;
    36                 }
    37             }
    38             vector<int> tmp;
    39             tmp=t[i];
    40             sort(tmp.begin(),tmp.end());
    41             maxx=-1;
    42             for(int j=1;j<=len;j++) {
    43                 for(int k=0;k+j-1<len;k++) {
    44                     if(tmp[k+j-1]-tmp[k]<5) {
    45                         maxx=max(maxx,j);
    46                         break;
    47                     }
    48                 }
    49             }
    50             if(flag) {
    51                 for(int j=0;j<len;j++) {
    52                     if(t[i][j]==1) {
    53                         t[i][j]=14;
    54                         break;
    55                     }
    56                 }
    57                 tmp=t[i];
    58                 sort(tmp.begin(),tmp.end());
    59                 for(int j=1;j<=len;j++) {
    60                     for(int k=0;k+j-1<len;k++) {
    61                         if(tmp[k+j-1]-tmp[k]<5) {
    62                             maxx=max(maxx,j);
    63                             break;
    64                         }
    65                     }
    66                 }
    67             }
    68             ans=max(maxx,ans);
    69         }
    70         printf("%d\n",5-ans);
    71     }
    72 }

**第x个数、敲7、集合运算、最长单词、Distribution**

暴力、模拟即可

转载于:https://www.cnblogs.com/ACMerszl/p/10697930.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/21e239cfeb5249bfb312980ce215df21.png