- define时间：
#define itn int
#define int long long
#define ind long double
#define yes cout << "Yes"
#define no cout << "No"
#define pii pair<long long, long long>
#define pci pair<char, int>
#define re return;
L. Recover Statistics
签到。
其中 Px 的意义为：数列中恰好有 x% 的数小于等于这个值。
void solve()
{cin >> x >> y >> z;cout << 100 << '\n';for (int i = 1; i <= 50; i++){cout << x << ' ';}for (int i = 51; i <= 95; i++){cout << y << ' ';}for (int i = 96; i <= 99; i++){cout << z << ' ';}cout << z + 1;
}
J. Grand Prix of Ballance
模拟。
看懂题目即可，注意一次只会开放一个关卡，后续的其他指令也只有关于这个关卡才会被响应。
pii sum[N];
set<int> st[N], st1[N];
void solve()
{cin >> n >> m >> k;for (int i = 1; i <= n; i++){fg[i] = 0;st[i].clear(); //记录有排名的st1[i].clear();//记录放弃的}for (int i = 1; i <= m; i++){sum[i].second = 0; //分数sum[i].first = i; //编号}int now;//记录当前关卡编号while (k--){int op;cin >> op >> x;if (op == 1){now = x;}else if (op == 2){cin >> y;if (now == y){if (st[y].find(x) == st[y].end() && st1[y].find(x) == st1[y].end()){sum[x].second += m - st[y].size();st[y].insert(x);}}}else{cin >> y;if (now == y){if (st[y].find(x) == st[y].end() && st1[y].find(x) == st1[y].end()){st1[y].insert(x);}}}}sort(sum + 1, sum + m + 1, [&](auto x, auto y){if(x.second != y.second) return x.second > y.second;return x.first < y.first; });for (int i = 1; i <= m; i++){cout << sum[i].first << ' ' << sum[i].second << '\n';}
}G. Expanding Array
void solve() {set<int>st;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-1;i++){x=a[i],y=a[i+1];z=x|y;st.insert(x);st.insert(y);st.insert(z);st.insert(x&y);st.insert(x^y);st.insert(z^x);st.insert(y^z);st.insert(0);}cout<<st.size();}
A. Arrow a Row
void solve()
{cin >> s1;num = 0;vector<pii> v;n = s1.size();for (auto i : s1){if (i == '-'){num++;}}cnt = 0;if (!num || n < 5){cout << "No";re;}if (s1[0] != '>' || s1.substr(s1.size() - 3, 3) != ">>>"){cout << "No";re;}for (int i = n - 1; i >= 0; i--){if (s1[i] == '>'){cnt++;}else{break;}}cout << "Yes ";for (int i = cnt; i > 3; i--){v.emplace_back(n - 4, 5);n--;}for (int i = 0; i < n - 3; i++){if (s1[i] == '>'){v.emplace_back(i + 1, n - i);}}cout << v.size() << '\n';for (auto j : v){cout << j.first << ' ' << j.second << '\n';}
}
I. Good Partitions
思维。
题意：给定一个数字序列和 \(k\) 次修改，每次修改 \(a[x]=y\)，有 \(k+1\) 次询问：
将序列分割为以 \(m\) 为间隔的小段，每小段满足非递减。问 \(m\) 可能的值有多少个。
思路：我们可以考虑如果 \(a[i-1]>a[i]\)，说明这个点将作为分割点，放入set。
又发现最后所有分割点应该具有相同的间隔，我们只可能将大段切成小段。
于是我们可以转化题意：
对于第一个出现的分割点，遍历他的因子；只有后续所有分割点都是因子的倍数，才是可能的 \(m\)。
vector<int> e[N+5];
void solve()
{set<int> st;cin >> n >> k;fill(b,b+N,0);for (int i = 1; i <= n; i++){cin >> a[i];}auto ck = [&](){if (st.empty()){return n;}ans = 0;auto minn = *st.begin();for (auto i : e[minn])//遍历第一个分割点的因子{if (b[1] == b[i])//所有分割点都是该因子的倍数等价于此式{ans++;}}return ans;};auto add = [&](int x){st.insert(x);for (auto j : e[x]){b[j]++;}};auto sub = [&](int x){st.erase(x);for (auto j : e[x]){b[j]--;}};for (int i = 2; i <= n; i++){if (a[i - 1] > a[i]){add(i - 1);}}cout << ck() << '\n';while (k--){cin >> x >> y;if (x > 1 && a[x - 1] > a[x]){sub(x - 1);}if (x < n && a[x] > a[x + 1]){sub(x);}a[x] = y;if (x > 1 && a[x - 1] > a[x]){add(x - 1);}if (x < n && a[x] > a[x + 1]){add(x);}cout << ck() << '\n';}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);/* solve(); */int T;T = 1;cin >> T;for (int i = 1; i <= N; i++)//预处理因子{for (int j = i; j <= N; j += i){e[j].emplace_back(i);}}while (T--){solve();}return 0;
}