标签：2024.12 10 cnt cout int cin long 周二 define
2024.12.10 周二
给你一个序列，你可以对这个序列中的每个数(0<=ai<100)进行拆分，使得最后整个序列单调不递减，询问是否有解。
给定一数组，可任意改变顺序，问是否可使a1%a2%a3%...%an!=0。
给定数组a,数字x,y。问<i,j>的对数使(ai+aj)%x==0,(ai-aj)%y==0。
有 n 条跑道，第 i 条跑道有 ai 节。给定整数 u，跑第 k 节会使分数加 u-k+1(有可能为负数)。给定 q 个询问，每个询问会给定l,u，求最小的 r，跑完l到r所有的跑道使得你得到的分数最大。
------------------------独自思考分割线------------------------
A1. 2点
1.发现如果有合法序列，一定是前一部分一位数，后一部分是两位数。
2.贪心去考虑分界线自然是越靠后越好。思路：维护前位最大值，ai能拆就拆，当不拆的时候依然<maxw则无解。然后代码分类讨论进行实现。小细节导致wa2发。
A2. 2点
1.妙妙题。排序后发现如果最小值唯一则存在。
2.最小值不唯一时：如果存在ai%a1!=0，则ai%a1<a1，为唯一最小值。当时猜对了，感觉是这样但是不能证明充要性。
A3. 2点
1.首先对于n^2种方案，要有一种遍历加快速统计配对数的思想。
2.对于满足条件的a,b：(a+b)%x=0,(a-b)%y=0，若a确定，则b满足b%x=(x-a%x)%x,b%y=a%y。数学题：同余还是有意思的，可以快速统计线性数。
A4. 3点
1.前缀和快速统计块数的和。
2.加分是关于块数单调递(关于跑道不连续)函数，快速找到最右侧的r使得获得的分数都是正的，使用二分。
3.如果r<n，考虑第r+1跑道,加分有正有负。r+2以后全是负数不再考虑。
------------------------代码分割线------------------------
A1.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n;
cin >> n;
int f = 1, maxw = 0;
while (n--)
{
int x;
cin >> x;
if (x < maxw)
f = 0;
if (!f)
continue;
if (x < 10)
{
maxw = x;
continue;
}
else
{
if (x / 10 <= x % 10 && x / 10 >= maxw)
maxw = x % 10;
else
maxw = x;
}
}
cout << (f ? "YES" : "NO") << endl;
}
A2.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n;
cin >> n;
map<int, int> cnt;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
cnt[x]++;
}
int minw = (*cnt.begin()).first;
int f = 0;
if (cnt[minw] > 1)
{
for (auto [x, cy] : cnt)
if (x % minw)
f = 1;
}
if (cnt[minw] == 1)
f = 1;
cout << (f ? "YES" : "NO") << endl;
}
A3.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n, x, y;
cin >> n >> x >> y;
int mul = x * y;
map<pair<int, int>, int> has;
int res = 0;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
// bug2(x - a % x, (x - a % x) % x); a==0时
res += has[{(x - a % x) % x, a % y}];
has[{a % x, a % y}]++;
}
cout << res << endl;
}
A4.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n;
cin >> n;
vector<int> pre(n + 2);
for (int i = 1; i <= n; i++)
cin >> pre[i], pre[i] += pre[i - 1];
int q;
cin >> q;
while (q--)
{
int L, u;
cin >> L >> u;
auto cal = [&](int cnt)
{
return (2 * u - cnt + 1) * cnt / 2;
};
auto cnt = [&](int i)
{
return pre[i] - pre[L - 1];
};
int l = L, r = n + 1;
while (r - l - 1)
{
int mid = l + r >> 1;
if (cnt(mid) <= u)
l = mid;
else
r = mid;
}
int R = l;
// bug(R);
if (R < n && cal(cnt(R + 1)) > cal(cnt(R)))
R++;
// bug2(cal(cnt(R + 1)), cal(cnt(R)));
cout << R << ' ';
}
cout << endl;
}
标签：2024.12,
10,
cnt,
cout,
int,
cin,
long,
周二,
define
From： https://www.cnblogs.com/jkkk/p/18599233