当前位置：首页 > news >正文

第十五周 6.6 --- 6.12

news 来源：原创 2024/5/19 1:34:15

6.6 --- 6.8

每天一门考试..

考得很萎靡...总之就是很颓...

所有的课都考完了...剩下的就是些课设和实验了..

end...

恩，接下来的时间就好好玩泥巴，该干嘛干嘛>.<

6.9

端午吃粽子 :D

cf 351 div2 d D - Bear and Two Paths

自己花式构造了一通然 wa

题解就是一幅图

没有想到这样在两边都搞成环/ TwT \

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 int n,k;
 9 int a,b,c,d;
10 
11 void solve(){
12     if(n == 4 || k < n+1){
13         puts("-1");
14         return;
15     }
16     vector<int> ans;
17     for(int i = 1;i <= n;i++){
18         if(i == a || i == b || i == c || i == d) continue;
19         ans.push_back(i);
20     }
21     printf("%d %d ",a,c);
22     for(int i = 0;i < ans.size();i++) printf("%d ",ans[i]);
23     printf("%d %d\n",d,b);
24 
25     printf("%d %d ",c,a);
26     for(int i = 0;i < ans.size();i++) printf("%d ",ans[i]);
27     printf("%d %d\n",b,d);
28 }
29 
30 int main(){
31     while(scanf("%d %d",&n,&k) != EOF){
32         scanf("%d %d %d %d",&a,&b,&c,&d);
33         solve();
34     }
35     return 0;
36 }

View Code

6.10

cf 349 div2 c 667C - Reberland Linguistics

in a row 的意思是连续，然后分 2 3 ；2 2； 3 2； 3 3这四种情况转移

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<set>
 7 using namespace std;
 8 
 9 const int maxn = 1e4+5;
10 char s[maxn];
11 int n;
12 int dp[maxn];
13 
14 void solve(){
15     if(n <= 5){
16         printf("0\n");
17         return;
18     }
19     memset(dp,0,sizeof(dp));
20     set<string> ans;
21     if(n-1 > 5){
22         dp[n-1] = 1;
23     }
24     if(n-2 > 5){
25         dp[n-2] = 1;
26     }
27     
28     string r1,r2;
29     if(dp[n-1]){
30         r1 += s[n-1];
31         r1 += s[n];
32         ans.insert(r1);
33     }
34     if(dp[n-2]){
35         r2 += s[n-2];
36         r2 += r1;
37         ans.insert(r2);
38     }
39     dp[n+1] = 1;
40     for(int i = n-2;i > 5;i--){
41         if(dp[i+2]){
42             string l,r;
43             l += s[i];l += s[i+1];
44             r += s[i+2];r += s[i+3];
45             if(l != r){
46                 dp[i] = 1;
47                 ans.insert(l);
48             }
49             if(dp[i+5]){
50                 dp[i] = 1;
51                 ans.insert(l);
52             }
53         }
54         if(dp[i+3]){
55             string lb,ub;
56             lb += s[i];lb += s[i+1];lb += s[i+2];
57             ub += s[i+3];ub += s[i+4];
58             if(i+5 <= n) ub += s[i+5];
59             if(lb != ub){
60                 dp[i] = 1;
61                 ans.insert(lb);
62             }
63             if(dp[i+5]){
64                 dp[i] = 1;
65                 ans.insert(lb);
66             }
67         }
68     }
69     
70     printf("%d\n",ans.size());
71     for(set<string>::iterator it = ans.begin();it != ans.end();++it){
72         string tmp = *it;
73         printf("%s\n",tmp.c_str());
74     }
75 }
76 
77 int main(){
78     while(scanf("%s",s+1) != EOF){
79         n = strlen(s+1);
80         solve();
81     }
82     return 0;
83 }

View Code

6.11

cf 348 div2 c 669C - Little Artem and Matrix

和之前一道题有点区别，之前bc 上那题只需要map映射下行，列最后变成了哪些行列

但是这题，填了值之后，还可以再变动

因为数据小，直接倒着做，暴力交换

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<map>
 7 using namespace std;
 8 
 9 typedef long long LL;
10 int g[105][105],n,m,q,cg[105][105];
11 const int maxn = 1e5+5;
12 
13 struct node{
14     int cmd,u,v,x;
15 }a[maxn];
16 
17 void solve(){
18     memset(g,0,sizeof(g));
19     for(int i = 1;i <= q;i++){
20         scanf("%d",&a[i].cmd);
21         if(a[i].cmd == 1 || a[i].cmd == 2){
22             scanf("%d",&a[i].x);
23         }
24         else scanf("%d %d %d",&a[i].u,&a[i].v,&a[i].x);
25     }
26 
27     for(int k = q;k >= 1;k--){
28         int cmd = a[k].cmd;
29         int u,v,x;
30         x = a[k].x;
31         memcpy(cg,g,sizeof(g));
32         if(cmd == 1){
33             for(int i = 1;i <= m;i++){
34                 int tmp = (i-1)%m;
35                 if(tmp == 0) tmp = m;
36                 g[x][i] = cg[x][tmp];
37             }
38         }
39         else if(cmd == 2){
40             for(int i = 1;i <= n;i++){
41                 int tmp = (i-1)%n;
42                 if(tmp == 0) tmp = n;
43                 g[i][x] = cg[tmp][x];
44             }
45         }
46         else {
47             u = a[k].u;v = a[k].v;
48             g[u][v] =x;
49         }
50 
51     }
52     
53     for(int i = 1;i<= n;i++){
54         for(int j = 1;j <= m;j++) {
55         //    printf("---g[%d][%d] = %d\n",i,j,g[i][j]);
56             printf("%d ",g[i][j]);
57         }
58         printf("\n");
59     }
60     
61 }
62 
63 int main(){
64     while(scanf("%d %d %d",&n,&m,&q) != EOF){
65         solve();
66     }
67     return 0;
68 }

View Code

6.12

其实还是做了题的..不过补的题还 T 着

6.13

继续T

6.14

好像一直很害怕写二叉树的题，不敢写，不会写...

必须要写的时候总是去粘以前的板..

说起来，还是大二下册学的二叉树...看紫薯一直看不明白

就在群里找了一个说话很随和的人小窗请教

芒果人真的好nice 啊！！！教我前序遍历中序遍历后序遍历...超级耐心

还鼓励我...每次讲完题都跟我说加油

话说都过去这么久了诶...真是怀念啊

sb 的我还是那么 sb ，不管什么方面，都 sb

不过...大概就是，现在做什么事都怀着我是 sb 的心态去做，反而更轻松了>.<

嘿嘿...还是惯例地干巴爹啊！！！

CCCC 玩转二叉树

比赛的时候看这题的时候只有1 个小时了，没反应过来镜面该怎么写，连板都没抄..

就是建树的时候 lch 和 rch 反一下就好

今天没有抄板...手推的/ w \

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 
 8 const int maxn = 1e5+5;
 9 int pre[105],in[105];
10 int n;
11 int lch[105],rch[105],vis[105];
12 
13 int Build(int l1,int r1,int l2,int r2){//l1 到 r1 是前序的
14     if(l1 > r1) return 0;               //l2 到 r2 是后序的
15     int root = pre[l1];
16     int p = l2;
17     while(in[p] != root) p++;
18     int cnt = p-l2;
19     rch[root] = Build(l1+1,l1+cnt,l2,p-1);
20     lch[root] = Build(l1+cnt+1,r1,p+1,r2);
21     return root;
22 }
23 
24 void bfs(int root){
25     queue<int> q;
26     memset(vis,0,sizeof(vis));
27     q.push(root);
28     vis[root] = 1;
29     vector<int> res;
30     while(!q.empty()){
31         int u = q.front();q.pop();
32         res.push_back(u);
33         if(lch[u] && !vis[lch[u]]){
34             q.push(lch[u]);
35             vis[lch[u]] = 1;
36         }
37         if(rch[u] && !vis[rch[u]]){
38             q.push(rch[u]);
39             vis[rch[u]] = 1;
40         }
41     }
42     for(int i = 0;i < res.size();i++){
43         printf("%d",res[i]);
44         if(i != res.size()-1) printf(" ");
45         else printf("\n");
46     }
47 }
48 
49 int main(){
50     while(scanf("%d",&n) != EOF){
51         for(int i = 0;i < n;i++) scanf("%d",&in[i]);
52         for(int i = 0;i < n;i++) scanf("%d",&pre[i]);
53         memset(lch,0,sizeof(lch));
54         memset(rch,0,sizeof(rch));
55         Build(0,n-1,0,n-1);
56     /*    for(int i = 1;i <= n;i++){
57             printf("lch[%d] = %d rch[%d] = %d\n",i,lch[i],i,rch[i]);
58         }*/
59         bfs(pre[0]);
60 
61     }
62     return 0;
63 }

View Code

cf 349div2 d 667D - World Tour

没有想到 n=3000 的话可以 n^2 log n 的预处理一下

然后还有就是，枚举两个点，然后剩余的就从之前每个点维护的三个点里面枚举，这样就降低复杂度了

为什么每个点都是维护三个点呢

因为如果当前确定的点是 abc了的话，c 如果只维护两个点恰好是 a，b的话，就找不够 4个点了

还有 T 了两天，是优先队列打错了..........

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<vector>
  7 #include<set>
  8 using namespace std;
  9 
 10 #define MP(a,b) make_pair(a,b)
 11 
 12 typedef pair<int,int> pii;
 13 const int maxn = 5005;
 14 int dis[maxn][maxn],first[maxn];
 15 int ecnt,n,m;
 16 const int INF = (1<<30)-1;
 17 
 18 struct Edge{
 19     int u,v,w;
 20     int nxt;
 21 }e[maxn*2];
 22 
 23 void Add_edge(int u,int v,int w){
 24     e[ecnt].v = v;
 25     e[ecnt].u = u;
 26     e[ecnt].w = w;
 27     e[ecnt].nxt = first[u];
 28     first[u] = ecnt++;
 29 }
 30 
 31 void init(){
 32     ecnt = 0;
 33     memset(first,-1,sizeof(first));
 34 }
 35 
 36 struct cmp{
 37     bool operator () (pii a,pii b){
 38         return a.first > b.first;
 39     }
 40 };
 41 
 42 void dij(int s){
 43     priority_queue<pii,vector<pii>,greater<pii> > PQ;
 44     for(int i = 1;i <= n;i++) dis[s][i] = INF;
 45     dis[s][s] = 0;
 46     PQ.push(MP(dis[s][s],s));
 47     while(!PQ.empty()){
 48         pii x = PQ.top();PQ.pop();
 49         if(dis[s][x.second] < x.first) continue;
 50         for(int i = first[x.second];i != -1;i = e[i].nxt){
 51             int v = e[i].v;
 52             if(dis[s][v] > dis[s][x.second]+e[i].w){
 53                 dis[s][v] = dis[s][x.second]+e[i].w;
 54                 PQ.push(MP(dis[s][v],v));
 55             }
 56         }
 57     }
 58 }
 59 
 60 int check(int x,int y,int u,int v){
 61     if(x == y || x == u || x == v || y == u || y == v || u == v) return 0;
 62     return 1;
 63 }
 64 
 65 void solve(){
 66     vector<pii> l[maxn],rl[maxn];
 67     for(int i = 1;i <= n;i++){
 68         dij(i);
 69         for(int j = 1;j <= n;j++){
 70             //printf("dis[%d][%d] = %d\n",i,j,dis[i][j]);
 71             if(i == j || dis[i][j] == INF) continue;
 72             l[i].push_back(make_pair(-1*dis[i][j],j));
 73             rl[j].push_back(make_pair(-1*dis[i][j],i));
 74         }
 75     }
 76     for(int i = 1;i <= n;i++) {
 77         sort(l[i].begin(),l[i].end());
 78         sort(rl[i].begin(),rl[i].end());
 79     }
 80 
 81     int ans = 0,res[4];
 82     for(int i = 1;i <= n;i++){
 83         for(int j = 1;j <= n;j++){
 84             if(dis[i][j] == INF || i == j ) continue;
 85             int s1 = rl[i].size();
 86             int s2 = l[j].size();
 87             for(int p1 = 0;p1 < min(3,s1);p1++){
 88                 for(int p2 = 0;p2 < min(3,s2);p2++){
 89                     pii x = rl[i][p1],y = l[j][p2]; 
 90                     int u = x.second;
 91                     int v = y.second;
 92                     if(!check(i,j,u,v)) continue;
 93                     int tmp = dis[u][i] + dis[i][j] + dis[j][v];
 94                     if(tmp > ans){
 95                         ans = tmp;
 96                         res[0] = u;res[1] = i;res[2] = j;res[3] = v;
 97                     }
 98                 }
 99             }
100         }
101     }
102     for(int i = 0;i < 4;i++) printf("%d ",res[i]);
103     printf("\n");
104 }
105 
106 int main(){
107     while(scanf("%d %d",&n,&m) != EOF){
108         init();
109         int u,v,w = 1;
110         for(int i = 1;i <= m;i++){
111             scanf("%d %d",&u,&v);
112             Add_edge(u,v,w);
113         }
114         solve();
115     }
116     return 0;
117 }

View Code

6.15

cf 347 div2 b B - Economy Game

昨晚写挂了...爆int ...还在犯这样的错...下次仔细仔细仔细再仔细

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 const int maxn = 1e5+5;
 9 int n,m;
10 
11 void solve(){
12     for(int a = 0;a <= 1000;a++){
13         LL l = a*1234567LL;
14         if(l > n) break;
15         for(int b = 0;b <= 10000;b++){
16             LL tot = a*1234567LL + b*123456LL;
17             if(tot > n) {
18                 break;
19             }
20             LL yu = 1LL*n-a*1234567LL-b*123456LL;
21             //printf("a = %d b = %d yu = %d\n",a,b,yu);
22             if(yu < 0LL) continue;
23             if(yu%1234 == 0){
24                 //printf("a = %d b = %d yu/1234 = %d",a,b,yu/1234);
25                 puts("YES");
26                 return;
27             }
28         }
29     }
30     puts("NO");
31 }
32 
33 int main(){
34     while(scanf("%d",&n) != EOF){
35         solve();
36     }
37     return 0;
38 }

View Code

然后 c wa 了好多发...原因都是读题不仔细！！！！！

想当然按照自己的想法去写自然 debug 不出来了....

读题仔细仔细

cf 347 div2 d D - Gifts by the List

题意杀..

给出一个森林，然后巴拉巴拉说了一通祖先的定义

然后每个人都有想送礼物的人，现在需要确定一个表，每个人送礼物是按照这个表来的，

比如当前点是 u ，在这个表里面的u 的第一个祖先就是u要送给礼物的人，问按照这个表来送礼物能否满足每个人送礼物的人是他想送的那个人

如果 a[u] = u ，肯定是可以的

如果 a[u] 和 a[fa[u]] 不同的话，肯定会矛盾，没有想出来，看的题解...（应该是和“第一个祖先” 那里再想下）

然后还有就是 dfs 到一个节点的时候，如果有别的点想要到它，就把它加进答案里。

不过怎么保证 u 就是后面想送它礼物那个点的祖先呢..不懂了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 const int maxn = 1e5+5;
 9 vector<int> g[maxn];
10 int n,m,a[maxn],vis[maxn],fa[maxn],in[maxn];
11 int ok,du[maxn],key[maxn];
12 vector<int> ans;
13 
14 void dfs(int u){
15     vis[u] = 1;
16     for(int i = 0;i < g[u].size();i++){
17         int v = g[u][i];
18         if(a[v] != a[u] && a[v] != v){
19             ok = 1;
20             return;
21         }
22         dfs(v);
23     }
24     if(key[u]){
25         ans.push_back(u);
26     }
27 }
28 
29 void solve(){
30     memset(vis,0,sizeof(vis));
31     ans.clear();
32     for(int i = 1;i <= n;i++){
33         if(!vis[i] && du[i] == 0){
34             ok = 0;
35             dfs(i);
36             if(ok){
37                 puts("-1");
38                 return;
39             }
40         }
41     }
42 
43     printf("%d\n",ans.size());
44     for(int i = 0;i < ans.size();i++) printf("%d\n",ans[i]);
45     
46 }
47 
48 int main(){
49     while(scanf("%d %d",&n,&m) != EOF){
50         for(int i = 1;i <= n;i++) g[i].clear();
51         int u,v;
52         memset(du,0,sizeof(du));
53         for(int i = 1;i <= m;i++){
54             scanf("%d %d",&u,&v);
55             g[u].push_back(v);
56             du[v]++;
57         }
58         
59         memset(key,0,sizeof(key));
60         for(int i = 1;i <= n;i++) scanf("%d",&a[i]),key[a[i]] = 1;
61         solve();
62     }
63     return 0;
64 }

View Code

6.16

应该也有写题...不过忘了

6.17

事情有点多...事情多的时候怎么才能够不烦呢....

6.18

看了下cf 357的题解...还没有敲

6.19

继续刷leetcode叭..

leetcode 144 Binary Tree Preorder Traversal

二叉树的前序遍历，递归实现就很简单了

 1 class Solution {
 2 public:
 3     vector<int> res;
 4     vector<int> preorderTraversal(TreeNode* root) {
 5         if(root != NULL) {
 6             res.push_back(root->val);
 7             preorderTraversal(root->left);
 8             preorderTraversal(root->right);
 9         }
10         return res;
11     }  
12 };