Practice III
前言
已将今天想吐槽的话放在第一题的思路1和2中
（明天是七夕，点首不悲伤的曲子嘻嘻）
Vladik and Complicated Book - CodeForces - 811B
题意
给定一个无重复数字的序列，给定q个询问，每个询问给定 L,R,x，其中 L <= x <= R，问若将下标[L, R]中的数字排序，下标为x的数字是否发生了改变
思路1 —— 莫队算法 + 树状数组
个人对本题怨念很深 ╭(╯^╰)╮
以下是今天训练时的想法：
首先规模给了10^4，那么如果数据非常极端的话，最大规模达到 10^8，对子区间排序必超时，暴力应该也会超时
那么应该思考以下，什么情况下该数字不变，自然是它在区间中的相对下标等于它是第几小数
于是问题转化为，多次询问下求给定区间的第K小数，可以用主席树，还可以用划分树，等等别的数据结构和算法
个人选用了莫队算法 + 树状数组
以权值为下标建树（树状数组），动态将该数加入时则+1，反之-1，那么对于每个询问可以二分是第几小数是几，再查询是否与对应位置上的数相同，相同为Yes，不同为No
耗时46ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
const int N = 1e4 + 15;
const int inf = 0x3f3f3f3f;
typedef unsigned long long ll;
struct node{
int l, r, id, k;
};
int tree[N];
int block_size;
node que[N];
int a[N];
int ans[N];
bool cmp(const node& a, const node& b){
if(a.l/block_size == b.l/block_size){
return a.r < b.r;
}else{
return a.l/block_size < b.l/block_size;
}
}
inline void init(){
memset(tree, 0, sizeof(tree));
}
inline int lowbit(int idx) { return (idx & -idx); }
int getSum(int idx){
int sum;
for(sum = 0; idx > 0; idx -= lowbit(idx)){
sum += tree[idx];
}
return sum;
}
void update(int idx, int val){
while(idx < N){
tree[idx] += val;
idx += (idx & -idx);
}
}
int getKth(int n, int k){
int l = 1, r = n;
int ans = n;
while(l <= r){
int m = (l + r) >> 1;
if(getSum(m) >= k){
ans = m;
r = m - 1;
}else{
l = m + 1;
}
}
return ans;
}
void add(int idx){ update(a[idx], 1); }
void del(int idx){ update(a[idx], -1); }
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
block_size = (int)sqrt(n);
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &que[i].l, &que[i].r, &que[i].k);
que[i].id = i;
}
sort(que + 1, que + m + 1, cmp);
int l = 1, r = 0;
for(int i = 1; i <= m; i++){
while(que[i].l < l) add(--l);
while(l < que[i].l) del(l++);
while(que[i].r < r) del(r--);
while(r < que[i].r) add(++r);
ans[que[i].id] = (getKth(n, que[i].k - que[i].l + 1) == a[que[i].k]);
}
for(int i = 1; i <= m; i++){
puts(ans[i] ? "Yes" : "No");
}
}
}
思路2 —— 逆序对（暴力）
比赛完才知道，10^8 规模竟然不会超时，还挺快
只能说CF的服务器太好了
想打人 →_→
按照思路1中第k小数的思路，不使用算法和数据结构优化，直接找就好了
耗时 93ms
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N];
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
while(m--){
int l, r, x;
int cnt = 0;
scanf("%d%d%d", &l, &r, &x);
for(int i = l; i <= r; i++){
if(a[i] <= a[x]) cnt++;
}
puts(x - l + 1 == cnt ? "Yes" : "No");
}
}
}
Vladik and Memorable Trip - CodeForces - 811C
题意
给定一个序列，要求选出若干个区间，他们的价值之和最大，要求选定的区间中出现的数必须全部在此区间中，区间的价值定义为区间中不同元素的异或和
思路
首先处理出如果要选定当前这个数，需要选定的区间是什么，再处理出这些区间的异或值
定义DP状态 dp[i] 表示选定第i个数时的最大价值，则DP方程为
if(i == dpl[a[i]]) dp[i] = max(dp[i + 1], dp[dpr[a[i]] + 1])，表示当i这一位置是当前数字所在区间的左端点时，可以选择不选这个数字或者选这个区间，其中取最大值
if(i != dpl[a[i]]) dp[i] = dp[i + 1]，表示若不为左端点，则只能不选
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <iomanip>
#include <vector>
using namespace std;
const int N = 5000 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N], l[N], r[N], xorsum[N];
int dpl[N], dpr[N];
int dp[N];
bool used[N];
int main(){
int n;
while(~scanf("%d", &n)){
memset(l, 0x3f, sizeof(l));
memset(r, 0, sizeof(r));
memset(dpl, 0x3f, sizeof(dpl));
memset(dpr, 0, sizeof(dpr));
memset(xorsum, 0, sizeof(xorsum));
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
l[a[i]] = min(l[a[i]], i);
r[a[i]] = max(r[a[i]], i);
}
for(int i = 0; i < N; i++){
for(int j = l[i]; j <= r[i]; j++){
dpl[i] = min(dpl[i], l[a[j]]);
dpr[i] = max(dpr[i], r[a[j]]);
}
}
for(int i = 0; i < N; i++){
memset(used, 0, sizeof(used));
for(int j = dpl[i]; j <= dpr[i]; j++){
if(used[a[j]] == true) continue;
xorsum[i] ^= a[j];
used[a[j]] = true;
}
}
for(int i = n - 1; i >= 0; i--){
if(i != n - 1) dp[i] = dp[i + 1];
if(i == dpl[a[i]]) dp[i] = max(dp[i], dp[dpr[a[i]] + 1] + xorsum[a[i]]);
}
printf("%d\n", dp[0]);
}
}
Roman Digits - CodeForces - 998D
题意
若用I表示1，V表示5，X表示10，L表示50，问由这四个罗马数字组成n位的不同的数字由多少种可能性（不考虑顺序，比如IX表示11，而不是9）
思路
没思路看了一下题解，有点令人发指呀
打表找规律
前面的数字是无规律的，直接保存结果，后面的数字构成49为公差的等差数列，输出公式
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
const int N = 1e6 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
ll num[] = {0, 4, 10, 20, 35, 56, 83, 116, 155, 198, 244, 292};
int main(){
ios::sync_with_stdio(false);
ll n;
while(cin >> n){
if(n <= 11) cout << num[n] << endl;
else cout << num[11] + (n - 11) * 49 << endl;
}
}
Taxes - CodeForces - 735D
题意
给定一个数n，可将其拆分为 n = n1 + n2 + … + nk，每一个数的价值定义为它的最大公因子，问价值之和最小值（可以不拆）
思路
哥德巴赫猜想
这个数如果是质数，显然答案就是1
如果本身不是质数，那么如果是偶数，根据哥德巴赫猜想，任意偶数可由两个质数相加而成，因此答案可以为2
如果是奇数，根据偶数+奇数=奇数，那么如果 2+x=这个数，而x是质数，答案可以为2，因为2是质数中唯一的偶数
而如果不行，那么答案就得为3了
你可能会问哥德巴赫猜想不是还没有证明吗
然而题目数据是有范围的
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 15;
const int inf = 0x3f3f3f3f;
bool isPrime(int n){
for(int i = 2; i*i <= n; i++){
if(n%i == 0) return false;
}
return true;
}
int main(){
int n;
while(~scanf("%d", &n)){
if(isPrime(n)) puts("1");
else if(n%2 == 0) puts("2");
else if(isPrime(n - 2)) puts("2");
else puts("3");
}
}
