题解：可以发现，我们此时的操作是将一段区间（不含端点）假如有数的话，就将其整体删除并在左右端点处加上1，根据我们学习的数据结构，其中有一个比较符合这种操作：珂朵莉树，也叫老司机树，他对于这种问题的做法是利用set，将该段区间整体从原来的地方划分出来，并将其删除，所以我们参考这种做法，将其删除：
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
struct node
{
int l, r, y;
inline bool operator<(const node&a)
{
return y < a.y;
}
}e[maxn];
int n, m;
void solve()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> e[i].l >> e[i].r >> e[i].y;
sort(e, e + m);
set<int>s;//应该可以像obt那样开结构体来处理，不过直接int也可以
for (int i = 1; i <= m; i++)
s.insert(i);
for (int i = 0; i < m; i++)
{
set<int>::iterator it = s.lower_bound(e[i].l);
if (it != s.end() && *it <= e[i].r)//存在时
{
set<int>::iterator it2= s.lower_bound(e[i].r);
s.erase(it, it2);
s.insert(e[i].l);
s.insert(e[i].r);
}
if (!s.size())//避免加下来查找不到
break;
}
cout << s.size() << endl;//将size直接当成答案
}
signed main()
{
int t;
cin >> t;
while (t–)
solve();
}
B：题目并没有要求我们要最小次数的翻转，所以我们先暴力将其全部翻转一次，看看能不能出现答案，假如并没有的话，就输出-1，此时翻转次数是有上限的，不太会证明，同时对于结果，我们假如翻转了奇数次，实际就为1次，偶数次就为0次
/*
题目并没有要求我们要最小次数的翻转，所以我们先暴力将其全部翻转一次，看看能不能出现答案，假如并没有的话，就输出-1，
此时翻转次数是有上限的，不太会证明，同时对于结果，我们假如翻转了奇数次，实际就为1次，偶数次就为0次
*/
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 2e2+10;
int n, m;
int a[maxn][maxn];
bool con[maxn], row[maxn];//代表此时行列是正是负
int ansr[maxn], ansc[maxn];//代表行列翻转次数
int flag = 0;//是否为正
bool check()//判断此时是否合法
{
for (int i = 1; i <= n; i++)
{
int sum = 0;
for (int j = 1; j <= m; j++)
sum += a[i][j];
if (sum < 0)
return 0;//代表不合法
}
for (int i = 1; i <= m; i++) //同理
{
int sum = 0;
for (int j = 1; j <= n; j++)
sum += a[j][i];
if (sum < 0)
return 0;
}
return 1;
}
void work()//进行翻转
{
for (int i = 1; i <= n; i++)row[i] = 0;
for (int i = 1; i <= m; i++)con[i] = 0;
for (int i = 1; i <= n; i++)
{
int sum = 0;
for (int j = 1; j <= m; j++)
sum += a[i][j];
if (sum < 0)
row[i] = 1;//代表此时要翻转
}
for (int i = 1; i <= n; i++)
{
if (row[i])
{
ansr[i]++;
for (int j = 1; j <= m; j++)
a[i][j] = -a[i][j];
row[i] = 0;
}
}
for (int i = 1; i <= m; i++)
{
int sum = 0;
for (int j = 1; j <= n; j++)
sum += a[j][i];
if (sum < 0)
con[i] = 1;
}
for (int i = 1; i <= m; i++)
{
if (con[i])
{
ansc[i]++;
for (int j = 1; j <= n; j++)
a[j][i] = -a[j][i];
con[i] = 0;
}
}
if (check())
{
flag = 1;
return;
}
}
void solve()
{
cin >> n >> m;
flag = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)cin >> a[i][j];
int tim = 1000;
while (tim–)
{
work();
if (flag == 1)
break;
}
if (!check()){
cout << “No” << endl;
}
else
{
cout << “Yes” << endl;
int k = 0;
for (int i = 1; i <= n; i++)
if (ansr[i] % 2)
k++;
cout << k << endl;
for (int i = 1; i <= n; i++)
{
if (ansr[i] % 2)
cout << i << ‘ ‘;
ansr[i] = 0;
}
cout << endl;
k = 0;
for (int i = 1; i <= m; i++)
if (ansc[i] % 2)
k++;
cout << k << endl;
for (int i = 1; i <= m; i++)
{
if (ansc[i] % 2)
cout << i << ‘ ‘;
ansc[i] = 0;
}
cout << endl;
}
}
signed main()
{
int t;
cin >> t;
while (t–)
solve();
}
C：签到的不能再签到
D:队友写的，也是比较签到的一题
E:要注意到范围限制，他最多有1e9，不能直接模拟，然后根据答案推一下结果就好了
F：签到的不能再签到
G：不会
H：比较好推的是根据组合数来推，当同时我们要注意，他的n是没有规定sum的，即要是一个一个求得话复杂度为：0(nT),所以我们必须找其他得路，通过对几组数据得模拟：利用组合数，不难发现其规律为：
ans[i]=ans[i-1]+ans[i-2]+1;
所以答案就出来了
I:不会
J:等下再补
K：
我是利用线段树来处理得，这题实验室每个人都有不同做法，不过我比赛是一个+=写为=，没发现一直错
我们对每个区间进行询问，找其他区间和他在一起的合法解，可以发现，要是一个区间和他是合法的话，必须保证后一个区间的l要大于前一个区间的r，同时他的贡献是由后一个区间的末尾到M距离*前一个区间的左端点到1的距离，所以我每次都将该贡献放在了区间左端点的上，在进行询问：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
struct node {
int l, r;
int val;
}tree[maxn << 2];
struct node1 {
int l, r;
inline bool operator<(const node1&p)const {
return l < p.l;
}
}e[maxn];
int a[maxn];
int q_mul(int a, int b)
{
a %= mod, b %= mod;
int ans = 0;
while (b)
{
if (b & 1)
{
ans = (ans + a) % mod;
}
b >>= 1;
a = (a + a) % mod;
}
return ans % mod;
}
void pushdown(int root)
{
tree[root].val = (tree[root << 1].val + tree[root << 1 | 1].val) % mod;
}
void build(int root, int l, int r){
tree[root].l = l, tree[root].r = r;
if (l == r)
{
tree[root].val = a[l] % mod;
return;
}
int mid = l + r >> 1;
build(root << 1, l, mid);
build(root << 1 | 1, mid + 1, r);
pushdown(root);
}
int query(int root, int ql, int qr){
int mid = (tree[root].l + tree[root].r) >> 1;
if (ql == tree[root].l&&qr == tree[root].r)
{
return tree[root].val%mod;
}
if (qr <= mid)
return query(root << 1, ql, qr);
else if (ql > mid)
return query(root << 1 | 1, ql, qr);
else
{
int ret = query(root << 1, ql, mid) % mod;
ret += query(root << 1 | 1, mid + 1, qr);
return ret % mod;
}
}
void solve(){
int n, m;
cin >> n >> m;
memset(a, 0, sizeof a);
for (int i = 1; i <= n; i++) {
cin >> e[i].l >> e[i].r;
a[e[i].l]+=(m – e[i].r + 1);
}
sort(e + 1, e + 1 + n);
build(1, 1, m);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (e[i].r + 1 <= m)
ans = (mod + q_mul(query(1, e[i].r + 1, m), e[i].l) + ans) % mod;
}
cout << ans << ‘\n’;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t–)
solve();
}
L:他有一个连续没看见，读了假题，换了好几种写法都没过，导致心态差点崩了（还是太菜，明年再争取icpc名额）
具体就是暴力就好了：
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 1e3 + 10;
int a[maxn];
int b[maxn];
int n, k;
bool cmp(int a, int b)
{
return a > b;
}
void solve(){
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> b[i];
int ans = 0;
int now = 1;
int cnt = 1;
a[1] = b[1];
if (b[n] % 2)
b[n + 1] = 0;
else
b[n + 1] = 1;
for (int i = 2; i <= n+1; i++){
if (b[i] % 2 == b[i – 1] % 2)
{
a[++cnt] = b[i];
}
else{
if (cnt <= k){
for (int j = 1; j <= cnt; j++){
ans += a[j];
}
}
else{
sort(a + 1, a + 1 + cnt, cmp);
for (int j = 1; j <= k; j++)
ans += a[j];
}
cnt = 1;
a[1] = b[i];
}
}
cout << ans << endl;
}
signed main()
{
int t;
cin >> t;
while (t–)
solve();
}
M:我们具体做法就是：首先可以发现，对于每一个合法对数都会在任意排序中出现一次，不过就是先后问题，比如：1 4 这两数会在任意序列中都出现，不过一半是1 4，一半是 4 1，这就比较好确定一点对于任意有意义的，在全排列中仅有一半是合法的：
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 1e5 + 20;
int f[maxn];
int inv[maxn];
int s[maxn];
const int mod = 1e9 + 7;
signed main()
{
for (int i = 1; i <= 100010; i++)
{
for (int j = 2; j*i <= 100100; j++)
f[i*j]++;//统计合法的
}
for (int i = 1; i <= 100010; i++)
s[i] = (s[i – 1] + f[i])%mod;//s[i]代表1-i中所有数合法的请款
inv[2] = 1;//直接在阶乘中/2
for (int i = 3; i < 100010; i++)
inv[i] = inv[i – 1] *i%mod;
int t;
cin >> t;
while (t–)
{
int n;
cin >> n;
if (n == 1)
{
cout << 0 << endl;
continue;
}
cout << inv[n] * s[n] % mod << endl;
}
}
总结：太菜了