-
东华码蹄集第21周oj赛（光潮的幻像，分苹果，马走日，码哥猜想）
小码哥在雪山闲逛的时候发现了一个神秘的序列。他发现如果按照一定的方式对这个序列进行操作，就可以得到一些隐藏的线索。这个序列含有n个整数，你需要对其进行m 次操作，操作分为两种:
1.给出下标α和整数y，将序列中的an替换为a y⒉给出下标a, g，求aag+1 …ay
其中为异或运算。
小码哥已经想到了一种使用线段树的解法。为了证明你的能力，你应当使用线段树以外的方法解决本题。
随便线段树或者树状数组维护一下区间异或值就好了，用cin会超时，这里用的快读/* * @Author: 西海为期 * @Date: 2022-10-21 19:48:37 * @Last Modified by: 西海为期 * @Last Modified time: 2022-10-21 19:48:37 */ #includeusing namespace std; const int maxn=1e6+100; typedef long long ll; const int inf=0x3f3f3f3f; int tree[maxn*4]; inline int read() { int x = 0,f = 1; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } void push(int i) { tree[i]=tree[i*2]^tree[i*2+1]; } void build(int root,int l,int r) { if(l==r) { tree[root]=read(); return ; } int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); push(root); } void updata(int root,int l,int r,int index,int x) { if(l==r) { tree[root]=tree[root]^x; return ; } int mid=(l+r)/2; if(index<=mid) updata(root*2,l,mid,index,x); else updata(root*2+1,mid+1,r,index,x); push(root); } int query(int root,int l,int r,int L,int R) { if(l>=L&&r<=R) { return tree[root]; } int mid=(l+r)/2; int res=0; if(mid>=L) res=res^query(root*2,l,mid,L,R); if(mid<R) res=res^query(root*2+1,mid+1,r,L,R); return res; } int main() { int n,m; //cout << (3 ^ 4 ^ 7 ^ 0) << endl; cin >> n >> m; build(1, 1, n); // cout << query(1, 1, n, 3, 6) << endl; int x, X, Y; for (int i = 1; i <= m;i++) { x = read(); X = read(); Y = read(); if(x==1) { updata(1, 1, n, X, Y); } else{ int ans = query(1, 1, n, X, Y); printf("%d\n", ans); } } //system("pause"); return 0; } /* 10 10 0 5 3 4 7 0 0 0 1 0 1 10 7 2 8 9 2 3 6 2 1 6 2 1 10 1 9 4 1 6 1 1 6 3 1 1 7 2 3 5 1 0 5 3 0 */ - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
二 分苹果
幼儿园里有N个小朋友(编号为1~N)，老师现在想要给这些小朋友们分苹果，要求每个小朋友都要分到苹果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明希望自己分到的苹果比小红的多，于是在分配苹果的时候，老师需要满足小朋友们的K个要求。幼儿园的苹果总是有限的，老师想知道他至少需要准备多少个苹果，才能使得每个小朋友都能够分到苹果，并且满足小朋友们所有的要求。
思路：拓扑排序判环，反向建图求每个点的高度，加起来/* * @Author: 西海为期 * @Date: 2022-10-21 20:48:37 * @Last Modified by: 西海为期 * @Last Modified time: 2022-10-21 21:38:10 */ #include#include #include #define pb push_back #define bp __builtin_popcount #define TIME cout << "RuningTime: " << clock() << "ms\n", 0 #define ls x<<1 #define rs x<<1|1 using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=1e5+10; const int MOD=9901; const int mod = 1e9+7; const double PI=3.14; int lowbit(int x){return x&-x;} ll gcd(ll x, ll y){ return y == 0 ? x : gcd(y, x%y); } ll lcm(ll x, ll y){ return x / gcd(x, y)*y; } inline ll dpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; } inline ll fpow(ll a, ll b,ll p){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % p; b >>= 1; t = (t*t) % p; }return r; } inline int read() { int x = 0,f = 1; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } int n, m, du[maxn], head[maxn], tot, cnt, ans[maxn], num[maxn]; struct node { int v, next; } edge[maxn]; queue<int>q; vector<int> G[maxn]; int leve[maxn]; int res = 0; void add(int u, int v) { edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot++; } void init() { tot = 0; memset(du, 0, sizeof(du)); memset(head, -1, sizeof(head)); } void topsort() { while(!q.empty()) { int u = q.front(); q.pop(); ans[cnt++]=u; for (int i = head[u] ; i != -1 ; i = edge[i].next) { du[edge[i].v]--; if (!du[edge[i].v]) q.push(edge[i].v); } } } void dfs(int now,int depth) { leve[now]=max(leve[now],depth); for (int i = 0; i < G[now].size();i++) { dfs(G[now][i], depth + 1); } } int main() { int x,y; cin >> n >> m; init(); for (int i = 1 ; i <= m ; i++) { int x, y; cin >> x >> y; add(x, y); du[y]++; num[x]++; G[y].pb(x); } for (int i = 1 ; i <= n ; i++) if (!du[i]) q.push(i); topsort(); if(cnt!=n) { cout << -1 << endl; return 0; } for (int i = 1; i <= n;i++) { if(num[i]==0) { dfs(i, 1); } } for (int i = 1; i <= n;i++) { res += leve[i]; } cout << res << endl; //system("pause"); return 0; } /* 3 3 1 2 2 3 1 3 6 */ - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
三 马走日
小码哥最近迷上了象棋，尤其是其中“马”这个棋子。
小码哥的棋盘由n＋1道水平线和n＋1道垂直线相交组成，水平线和垂直线分别各自标上O到n的序号。
棋子可以落在水平线和垂直线的交叉点上，每个交叉点由其所在水平线和垂直线的编号而获得一个坐标(a, g)。
象棋中的马走“日”，即沿着一个1×2的“日”字形的对角线移动，比如从(1，0)移动到(3，1)。
现在假设整个棋盘上只有一个“马”在(a,b)处，小码哥想知道这个马跳到他指定的某个位置最少需要跳几步。
提前BFS跑出来所有解就行了，每次询问都跑BFS会TLE/* * @Author: 西海为期 * @Date: 2022-10-21 22:00:16 * @Last Modified by: 西海为期 * @Last Modified time: 2022-10-21 22:22:14 */ /* * @Author: 西海为期 * @Date: 2022-10-21 22:00:16 * @Last Modified by: 西海为期 * @Last Modified time: 2022-10-21 22:22:14 */ #include#include #include #define pb push_back #define bp __builtin_popcount #define TIME cout << "RuningTime: " << clock() << "ms\n", 0 #define ls x<<1 #define rs x<<1|1 using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=1e5+10; const int MOD=9901; const int mod = 1e9+7; const double PI=3.14; int lowbit(int x){return x&-x;} ll gcd(ll x, ll y){ return y == 0 ? x : gcd(y, x%y); } ll lcm(ll x, ll y){ return x / gcd(x, y)*y; } inline ll dpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; } inline ll fpow(ll a, ll b,ll p){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % p; b >>= 1; t = (t*t) % p; }return r; } typedef pair<int, int>PII; queue<PII>q; const int N = 501; int n; int d[N][N]; int dx[8] = { -2,-2,-1,-1,1,1,2,2 }; int dy[8] = { 1,-1,2,-2,2,-2,1,-1 }; inline int read() { int x = 0,f = 1; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } void bfs() { while (q.size()) { PII t = q.front(); q.pop(); int x = t.first, y = t.second; for (int i = 0; i < 8; i++) { int tx = x + dx[i]; int ty = y + dy[i]; if (d[tx][ty] != -1 || tx < 0 || ty < 0 || tx > n || ty > n) continue; else { d[tx][ty] = d[x][y] + 1; q.push({ tx,ty }); } } } } int main() { cin >> n ; int a, b; cin >> a >> b; memset(d, -1, sizeof d); d[a][b] = 0; q.push({ a,b }); bfs(); int q; cin >> q; int x, y; while (q--) { x=read(); y=read(); printf("%d\n", d[x][y]); } //system("pause"); return 0; } /* 2 0 0 3 1 1 2 2 0 1 -1 4 3 */ /* 2 0 0 3 1 1 2 2 0 1 -1 4 3 */ - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
四 码哥猜想
小码哥第一次看到了”角谷猜想”∶
“对于任意一个正整数，如果是奇数，则乘3加1，如果是偶数，则除以2，得到的结果再按照上述规则重复处理，最终总能够得到1。”
数学的简洁与优美让小码哥惊叹不已，小码哥大受启发，提出了”码哥猜想”:
“对于100以内(包括100)任意一个正整数，如果是奇数，则乘5减1，如果是偶数，则除以2，得到的结果再按照上述规则重复处理，最终总能够得到1。”
很不幸，小码哥发现自己的猜想对于100以内的正整数并不是完全成立，于是小码哥想求出100以内满足自己猜想的正整数，来研究其性质，你来帮帮他吧。
暴力算，中间结果大于1e7的pass掉/* * @Author: 西海为期 * @Date: 2022-10-21 22:48:49 * @Last Modified by: 西海为期 * @Last Modified time: 2022-10-21 22:48:49 */ #include#include #include #define pb push_back #define bp __builtin_popcount #define TIME cout << "RuningTime: " << clock() << "ms\n", 0 #define ls x<<1 #define rs x<<1|1 using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=1e5+10; const int MOD=9901; const int mod = 1e9+7; const double PI=3.14; int lowbit(int x){return x&-x;} ll gcd(ll x, ll y){ return y == 0 ? x : gcd(y, x%y); } ll lcm(ll x, ll y){ return x / gcd(x, y)*y; } inline ll dpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; } inline ll fpow(ll a, ll b,ll p){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % p; b >>= 1; t = (t*t) % p; }return r; } inline int read() { int x = 0,f = 1; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } int solve(int x) { map<int, int> vis; while(1) { if(x==1) return 1; if(vis[x]==1||x>=1e7) return 0; vis[x] = 1; if(x&1) x = x * 5 - 1; else x = x / 2; } } int main() { for (int i = 1; i <= 100;i++) { if(solve(i)) cout << i << " "; } //system("pause"); return 0; } /* 3 3 1 2 2 3 1 3 6 */ - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
-
相关阅读:
jwbasta-Springboot集成Quartz
d3dx9_42.dll丢失怎么解决？有什么方法解决d3dx9_42.dll丢失问题
vue项目中使用本地下载的iconfont文件中的图标，全部显示的都是方框
C/C++问题：一个指针的大小是多少？怎么理解指针变量的存在
这是不是你们都在找的免费又好用的配音网站？
软考-软件项目活动图详解
多线程学习-线程池
补充d2l.torch库里面缺失train_ch3函数
模板方法模式
srs webrtc推拉流环境搭建(公网)
- 原文地址：https://blog.csdn.net/s1050712899/article/details/127455238
