-
码蹄集oj赛第25周（cup，查询，捕鱼，射线的交，平衡）
cup
思路：树状数组求逆序数
/* * @Author: 晚乔最美 * @Date: 2022-11-17 14:44:26 * @Last Modified by: 晚乔最美 * @Last Modified time: 2022-11-17 15:44:26 */ #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=5e5; const int MOD=1e9+7; 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 r = 1, t = a; while (b){ if (b & 1)r = (r*t); b >>= 1; t = (t*t); }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; } struct node{ int num, id; } st[maxn], a[maxn]; int n; int tree[maxn], tmp[maxn]; bool cmp(node a,node b) { if(a.num==b.num) return a.id < b.id; return a.num < b.num; } void add(int k,int x){ while (k<=n) { tree[k] += x; k += lowbit(k); } } int getsum(int k){ int ans = 0; while (k) { ans += tree[k]; k -= lowbit(k); } return ans; } int main(){ ll sum = 0; cin >> n; for(int i=1;i<=n;i++){ st[i].num = read(); st[i].id = i; a[i].num = st[i].num; a[i].id = st[i].id; } int flag = 1; for (int i = 2; i <= n; i++) if(st[i].num<st[i-1].num) flag = 0; if(flag){ cout << 0 << endl; return 0; } sort(st+1,st+n+1,cmp); int l=0, r=0, p1=0, p2=0; // 1 2 3 // 3 2 1 // 1 2 3 for (int i = 1; i <= n; i++) { //l = min(l, i - st[i].id); // cout << i << " " << st[i].id << endl; if (i - st[i].id < l) { l = i - st[i].id; p1 = st[i].id; } if ( i - st[i].id> r) { r = i - st[i].id; p2 = st[i].id; } } //cout << p1 << " " << p2 << endl; //swap(a[p1], a[p2]); node t = a[p1]; node y = a[p2]; a[p1].num = y.num; a[p2].num = t.num; sort(a + 1, a + n + 1, cmp); for (int i = 1; i <= n; i++) { tmp[a[i].id] = i; } for (int i = 1; i <= n;i++) { add(tmp[i], 1); sum += i - getsum(tmp[i]); } cout << sum + 1 << endl; //system("pause"); return 0; } /* 5 3 5 4 1 2 5 3 3 2 1 1 */ - 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
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
查询
硬哥写的
思路：暴力，懂得都懂
/* * @Author: 硬哥 * @Date: 2022-11-19 14:44:26 * @Last Modified by: 硬哥 * @Last Modified time: 2022-11-19 15:44:26 */ #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=5e5; const int MOD=1e9+7; 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 r = 1, t = a; while (b){ if (b & 1)r = (r*t); b >>= 1; t = (t*t); }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 num[maxn]; int main( ) { int n; cin>>n; for(int i=1;i<=n;i++) cin>>num[i]; int q,op,op1,op2,a,b,c,d,res; cin>>q; for(int i=0;i<q;i++){ res=0; cin>>op; if(op==1){ cin>>op1>>op2; num[op1] = op2; continue; }else{ cin>>a>>b>>c>>d; for(int j=a;j<=b;j++){ if(num[j]>=c&&num[j]<=d) res++; } } cout<<res<<endl; } return 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
捕鱼
思路：贪心
#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=3e4+10; const int MOD=9901; const int mod = 1e9+7; const double PI=3.14; const double Exp = 1e-9; 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 r = 1, t = a; while (b){ if (b & 1)r = (r*t); b >>= 1; t = (t*t); }return r; } struct node{ double l, r; int x; } a[maxn]; bool cmp(node p,node q) { return p.l < q.l; } int main() { int n, d; cin >> n >> d; int flag = 1; for (int i = 1; i <= n;i++) { double x, y; cin >> x >> y; if(y>d) flag = 0; double l = sqrt(d * d - y * y); a[i].l = x - l; a[i].r = x + l; a[i].x = x; } if(flag==0) { cout << -1 << endl; //system("pause"); return 0; } sort(a + 1, a + 1 + n, cmp); double now=a[1].r; int ans=1; for (int i = 2; i <= n;i++) { if (a[i].l > now + Exp) { ans++; now = a[i].r; }else if (a[i].r < now + Exp) { now = a[i].r; } } cout << ans << endl; //system("pause"); return 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
射线的交
#includeusing namespace std; typedef struct data{ int x; int y; char z; }; int main( ) { int n,res; data S; vector<data> s1,s2; cin>>n; for(int i=0;i<n;i++) { cin>>S.x>>S.y>>S.z; if(S.z == 'U' || S.z == 'D') s1.push_back(S); //s1存放与y轴平行的射线 else s2.push_back(S); //s2存放与x轴平行的射线 } for(int i=0;i<s1.size();i++) { for(int j=0;j<s2.size();j++) { if(s1[i].z == 'U') { if(s2[j].z == 'R') { if(s1[i].x >= s2[j].x && s1[i].y <= s2[j].y) res++; } else { if(s1[i].x <= s2[j].x && s1[i].y <= s2[j].y) res++; } } else { if(s2[j].z == 'R') { if(s1[i].x >= s2[j].x && s1[i].y >= s2[j].y) res++; } else { if(s1[i].x <= s2[j].x && s1[i].y >= s2[j].y) res++; } } } } cout<<res; return 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
平衡
差分搞一搞
/* * @Author: SoftWare_Cute * @Date: 2022-11-19 20:41:17 * @Last Modified by: SoftWare_Cute * @Last Modified time: 2022-11-19 20:41:17 */ #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 int SoftWare_Cute_YYDS = 84728493; 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 f[maxn]; int main() { string str; cin >> str; int ans = 0; for (int i = 0; i < str.length();i++) { //if(str[i]=='0')continue; if(i!=0) f[i] += f[i - 1]; int now = (f[i] + str[i]+SoftWare_Cute_YYDS) % 3; if(now==0) continue; else if(now==1) { f[i + 1]--; ans++; } else{ f[i + 1]++; ans++; } } cout << ans << endl; //system("pause"); return 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
-
相关阅读:
.Net+Vue3实现数据简易导入功能
vue3学习（十一）--- v-model
EntityFrameworkCore 模型自动更新（下）
默认为4G网络
神经网络的图像识别技术,人工神经网络图像识别
Python 猫的 2023 年终回顾
dotnet 控制台 使用 Microsoft.Maui.Graphics 配合 Skia 进行绘图入门
专业运动耳机哪个牌子好、专业运动耳机推荐
前端 JS 经典：ES6 和 CommonJs 用法
2022杭电多校十 1004-Average Replacement（猜结论+并查集）
- 原文地址：https://blog.csdn.net/s1050712899/article/details/127941769
