排列组合的定义是什么？

什么情况下会达到最大？

和​和序列最大值的关系是什么？

或运算的特点是什么？

或运算的基本定律有什么？

设序列最大值为，异或最大值如何通过或运算求得？设异或最大值（目标值）为，在题目保证已经有解得条件下，方程和方程​解集是否有交集？交集必定含有谁？

显然，或运算中，对评测机的提问是

这意味着，第一轮我们执行类型的提问，可以在次之内找寻到序列的最大值。

显然，可以通过和一个数异或得到。

问题是，是多少？

通过上述内容发现，我们可以执行$a_i | p_{max}  ? a_k | p_{max} n-1maxxor$以及

​ 异或线性方程 的解集

最后一步，遍历解集范围，找到任意一个满足即可。实际上，可以直接找解集范围内最小的，因为最小的必然与​按位互补，否则必定不是最小的。

综上所述，在最坏的​次询问下，必然可以得出结果。

#include <bits/stdc++.h>
using namespace std;
int question1(int a, int b)
{
    cout << "? " << a << " " << a << " " << b << " " << b << endl;
    char c;
    cin >> c;
    if (c == '<')
        return b;
    return a;
}
char question2(int a, int b, int location)
{
    cout << "? " << a << " " << location << " " << location << " " << b << endl;
    char c;
    cin >> c;
    return c;
}
int question3(int a, int b)
{
    cout << "? " << a << " " << a << " " << b << " " << b << endl;
    char c;
    cin >> c;
    if (c == '<')
        return a;
    return b;
}
void solve()
{
    int n;
    cin >> n;
    int location = -1;
    cout << "? 0 0 1 1" << endl;
    char c;
    cin >> c;
    if (c == '<')
        location = 1;
    if (c == '>')
        location = 0;
    for (int i = 2; i <= n - 1; i++)
    {
        location = question1(location, i);
    }
    // 已询问n-1次
    int t = 0, maxxor = 0;
    int x = n - 1;
    while (x)
    {
        t++;
        x >>= 1;
    }
    for (int i = 0; i < t; i++)
        maxxor += (1 << i);
    // finalmax
    // cout << location << " " << maxxor << endl;
    vector<int> ans;
    ans.push_back(0);
    for (int i = 1; i <= n - 1; i++)
    {
        char c = question2(ans[0], i, location);
        if (c == '=')
        {
            ans.push_back(i);
        }
        else if (c == '<')
        {
            ans.clear();
            ans.push_back(i);
        }
        else
            continue;
    }
    // 已询问2n-2次
    int pos = -1;
    for (auto &p : ans)
    {
        if (pos == -1)
            pos = p;
        else
        {
            pos = question3(pos, p);
        }
    }
    cout << "! " << pos << " " << location << endl;
    return;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

怎样差异化最大？和最小值与最大值有没有关系？

排序之后

​

想快点。。。

人民币曾经发行的面值是，有什么特点？

能不能直接贪心？为什么？如果加一个元面值的纸币呢？

建议看官网的贪心正确性证明，这里只讨论取倍数的问题。显然单位元为最小公倍数，超过的即可分块贪心。

之内打表，之外的计算倍数。

显然，需要计算取多少次会让金额降到以下。

结果为

根据样例不难想到肯定要问一个角​，询问后的结果意义是什么？

询问该直线和边的两个交点（注意坐标计算的问题），又得到了什么信息？

什么条件下，这里已经可以终止询问了？

询问得到的直线上必定至少有一个雷存在。询问两个角得到的坐标又会得到两条直线构成一个草字头形状"艹"，这里就会得到两个坐标。再随便挑一个问，是就是答案，否则是另一个。

为什么说问三次就行，因为如果和的询问结果是奇数，会导致坐标为小数（曼哈顿距离在直线上走格子必定是偶数），这显然不可能是雷，只可能是另一个。但这样会无端增加代码量，所以就不如不实现这个特判。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> p;
int d1, d2, d3, d4;
int n, m;
p l, r;
void readfirst()
{
    cout << "? " << 1 << " " << 1 << endl;
    cin >> d1;
    l = {d1 + 1, 1};
    r = {1, d1 + 1};
    if (l.first > n)
    {
        l.first = n;
        l.second = d1 + 2 - n;
    }
    if (r.second > m)
    {
        r.second = m;
        r.first = d1 + 2 - m;
    }
    cout << "? " << l.first << " " << l.second << endl;
    cin >> d2;
    cout << "? " << r.first << " " << r.second << endl;
    cin >> d3;
    return;
}
void solve()
{

    cin >> n >> m;
    int maxp = n + m - 2;
    readfirst();
    if (d2 & 1)
    {
        int y = (d1 + 2 + r.second - r.first - d3) / 2;
        int x = d1 + 2 - y;
        cout << "! " << x << " " << y << endl;
        // return;
    }
    else if (d3 & 1)
    {
        int y = (d1 + 2 + d2 + l.second - l.first) / 2;
        int x = d1 + 2 - y;
        cout << "! " << x << " " << y << endl;
    }
    else
    {
        int y1 = (d1 + 2 + r.second - r.first - d3) / 2;
        int x1 = d1 + 2 - y1;
        int y2 = (d1 + 2 + d2 + l.second - l.first) / 2;
        int x2 = d1 + 2 - y2;
        cout << "? " << x1 << " " << y1 << endl;
        int d4;
        cin >> d4;
        if (d4 == 0)
        {
            cout << "! " << x1 << " " << y1 << endl;
        }
        else
            cout << "! " << x2 << " " << y2 << endl;
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

是否一定有解？呢？呢？呢

tips：他们都是特殊的二进制数。

最高位和​不同时是否一定有解？最高位若是相同呢？

除最高位之外，注定和的首个不同位一定是

要随时保证，在对位置进行换操作后，保持前面的高位不动，最大能被更新成多少？

首先目标值​​时必定无解。

其次，样例不难得出必然无解。

仅讨论且的情况分析。

本体讨论时从最高位向最低位讨论，位指针单调递减。

若最高位和​相同时是一定有解而且可以一步到达的，因为的最高位必定是，小于，此时直接用更新，一步结束。

若最高位和不同时，显然，，一步是不可能达到的。

先考虑将最高位降成相同的。

这时如果后面和都相同，的剩余位保持就行（)

如果第一个不同的位为，若将，此时必然，无解。

此时若第一步将置于，第二步同样无法实现将置为，治标不治本，只是拖延问题发生的时间。

所以第一个不同的位为时无解。

相反，若第一个不同的位为，置，则此时必定保证了，后面的位随便设置都不会改变结果。

因此，后面的错分设位，让部分的,即形成如下形态的数： 此时必然能在一步之内直接完成。

综上所述，最少在​即可保证完成任务。

还有就是，题没有问你要选择那个数来进行异或，只要你给出操作过后的值，省事。

其实问的话也不费事而已，就多了一步。要先求选择异或的数再计算操作后的值会涉及大量的变位操作，实现繁琐而且容易出错。

#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int, int> power;
int get_highest_one(int x)
{
    for (int i = 62; i >= 0; i--)
    {
        if ((x >> i) & 1)
            return 1;
    }
    return -1;
}
void init()
{
    for (int j = 0; j <= 62; j++)
    {
        power[(1LL << j)] = 1;
    }
}
void solve()
{
    int n, m;
    cin >> n >> m;
    int t = 0;
    while ((1LL << t) <= n)
    {
        t++;
    }
    if (power[n])
    {
        cout << -1 << endl;
        return;
    }
    if ((n ^ m) < n)
    {
        cout << 1 << endl;
        cout << n << " " << m << endl;
        return;
    }
    for (int i = t - 2; i >= 0; i--)
    {
        if (((n >> i) & 1) != ((m >> i) & 1))
        {
            if (((m >> i) & 1))
            {
                cout << -1 << endl;
                return;
            }
            else
            {

                int ans = 0;
                for (int j = 0; j <= i; j++)
                {
                    ans += (1LL << j);
                }
                cout << 2 << endl;
                cout << n << " " << ans << " " << m << endl;
            }
            return;
        }
    }
    return;
}
signed main()
{
    init();
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

如果存在可能的分法，每一段的是否是全局的？

分两组就够了。如何判断能分成两组？

对于问题而言，如果有解得话，全局的即是局部的​.

开桶爆搜全局得到，然后从头开始尝试分一组出来满足.

如果这一组直接分完了才是，无解。

否则，若剩下的一组查询完和不等，无解。

否则是可能的一种分法​.

写法上，可以分两段爆搜出两组最小,如果出现了交集则无解。

#include <bits/stdc++.h>
using namespace std;
int a[200001];
void solve()
{
    map<int, bool> mp;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mp[a[i]] = 1;
    }
    int mex = 0;
    for (int i = 0; i < n; i++)
    {
        if (mp[i] == 0)
        {
            mex = i;
            break;
        }
    }
    int l = 1;
    map<int, bool> mp1, mp2;
    bool tag1 = 0;
    for (l; l <= n; l++)
    {
        mp1[a[l]] = 1;
        if (mp1.size() >= mex)
            for (int i = 0; i <= mex; i++)
            {
                if (i == mex)
                {
                    if (mp1[i] == 0)
                        tag1 = 1;
                }
                else if (mp1[i] == 0)
                {
                    break;
                }
            }
        if (tag1)
            break;
    }
    if (l >= n)
    {
        cout << -1 << endl;
        return;
    }
    for (int i = l + 1; i <= n; i++)
        mp2[a[i]] = 1;
    for (int i = 0; i <= mex; i++)
    {
        if (i == mex)
        {
            if (mp2[i] == 0)
            {
                cout << 2 << endl;
                cout << 1 << " " << l << endl;
                cout << l + 1 << " " << n << endl;
            }
            else
                cout << -1 << endl;
        }
        else if (mp2[i] == 0)
        {
            cout << -1 << endl;
            return;
        }
    }
    return;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

随机抓一组数据的情况下，如何让函数的结果最小？

对于都相同的一组数据，其结果等于多少？

优先塞小的信息，但是第一关键字排序是,可能后面大的小，能塞下的更多，怎么办？

对于随机抓的一组数据，必然是有序的情况下达到最小结果。

那么相同的情况下，肯定优先塞小的短信。

以为第一关键字，​为第二关键字排序之后进行贪心.

选择后的最优结果为 初始时，顺序暴力选定基底若基底都大了直接下一个，否则奠定整个函数计算的后开始贪心：

首先将相同的全部选起来直到达到时间上界，选择.

（注意，因为基底的要求，不能入堆）

这个时候有个问题，后面还有更大但更小的，这种数可能会在空间中塞下更多的数。

解决办法就是本周的关键算法——反悔贪心。

在付出一定的代价之后可以选择比不付出代价更小且更实惠的，我们就反悔上一次对的选择。

反悔谁呢？

反悔占地方最大的那个！

所以使用大根堆维护已选的​.

如果反悔一次后可以塞入就塞入，反悔了后还是塞不进去就放弃这个（因为牺牲个换个一定是亏损的）

双层暴力加堆操作，时间复杂度。

以为第一关键字，为第二关键字排序.

设表示“选择编号中的条信息，信息以结尾所花的时间”。

则有方程： 边界条件 答案计算：时维护最大​.

维度优化：暴力时就记忆

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 20001;
pair<int, int> p[maxn]; //{b,a}
int id[maxn];
void solve()
{
    int n, l;
    cin >> n >> l;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].second >> p[i].first;
    }
    sort(p + 1, p + 1 + n);
    int size_final = 0, now = 0;
    p[n + 1] = {0, 0};
    id[n + 1] = n + 1;
    for (int i = n; i >= 1; i--)
    {
        if (p[i].first == p[i + 1].first)
            id[i] = id[i + 1];
        else
            id[i] = i + 1;
    }
    for (int i = 1; i <= n; i++)
    {
        int nowb = p[i].first;
        int nowa = p[i].second;
        if (nowa > l)
            continue;
        priority_queue<int> q;
        int ans = nowa;
        for (int j = i + 1; j < id[i]; j++)
        {
            if (ans + p[j].second <= l)
            {
                ans += p[j].second;
                q.push(p[j].second);
            }
            else
                break;
        }
        int size = q.size() + 1;
        for (int j = id[i]; j <= n; j++)
        {
            if (nowb != p[j].first)
            {
                ans += p[j].first - nowb;
                nowb = p[j].first;
            }
            while (!q.empty() && ans > l)
            {
                ans -= q.top();
                q.pop();
            }
            if (ans + p[j].second <= l)
            {
                ans += p[j].second;
                q.push(p[j].second);
            }
            else
            {
                if (!q.empty())
                {
                    if (p[j].second < q.top())
                    {
                        ans -= q.top();
                        q.pop();
                        ans += p[j].second;
                        q.push(p[j].second);
                    }
                }
            }
            size = max(size, (int)q.size() + 1);
        }
        size_final = max(size_final, size);
    }
    cout << size_final << endl;
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
using p = pair<int, int>;
const int maxn = 5001;
const int INF = numeric_limits<int>::max();
const int inf = numeric_limits<int>::min();
int n, l;
int a[maxn], b[maxn];
p pd[maxn];
int dp[maxn][maxn];
void solve()
{
    cin >> n >> l;
    for (int i = 1; i <= n; i++)
    {
        cin >> pd[i].second >> pd[i].first;
    }
    sort(pd + 1, pd + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        a[i] = pd[i].second;
        b[i] = pd[i].first;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        dp[1][i] = a[i];
        ans = max(dp[1][i] <= l ? 1LL : 0LL, ans);
    }
    for (int i = 2; i <= n; i++)
    {
        int mintime = INF;
        for (int j = i; j <= n; j++)
        {
            mintime = min(dp[i - 1][j - 1] - b[j - 1], mintime);
            dp[i][j] = mintime + b[j] + a[j];
            ans = max(dp[i][j] <= l ? i : inf, ans);
        }
    }
    cout << ans << endl;
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

容斥原理。

且的部分怎么算？如果没有限制条件呢？

容斥原理，单独算就完了。

的部分总共有个

总共有​个

容斥部分且，共​个（可以选自己）

如果去掉条件保证,发生的变化详见代码。

#pragma GCC Optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 300001;
int a[maxn];
void solve()
{
    int n, c;
    cin >> n >> c;
    int even = 0, odd = 0;
    int ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
    vector<int> ji;
    vector<int> ou;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] & 1)
        {
            ji.push_back(a[i]);
        }
        else
            ou.push_back(a[i]);
        int f1 = c - a[i] + 1;
        if (f1 >= 0)
            ans1 += f1;
        if (a[i] <= c)
            ans2 += (a[i] / 2 + 1);
        else if (a[i] > c && a[i] <= 2 * c)
        {
            ans2 += (c - a[i] / 2 + 1);
        }
    }
    int size1 = ji.size(), size2 = ou.size();
    set<pair<int, int>> s;
    for (int i = 0; i < size1; i++)
    {
        if (ji[i] > c)
            break;
        int p = upper_bound(ji.begin(), ji.end(), 2 * c - ji[i]) - ji.begin();
        ans3 += p - i;
    }
    for (int j = 0; j < size2; j++)
    {
        if (ou[j] > c)
            break;
        int p = upper_bound(ou.begin(), ou.end(), 2 * c - ou[j]) - ou.begin();
        ans4 += p - j;
    }
    cout << (c + 1) * (c + 2) / 2 - (ans1 + ans2 - (ans3 + ans4)) << endl;
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

爆搜可不可行？最坏的时间复杂度是多少？

像不像背包？

按层字符串位数。

设表示“前层匹配长度字符串所花费的价值”

则有转移方程

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int mod = 998244353;
const int maxn = 201;
using p = pair<int, int>;
string T;
int n;
vector<int> sizer(101);
vector<string> a[1001];
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr)
int dp[maxn][maxn];
int main()
{
    IOS;
    cin >> T;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> sizer[i];
        // a[i].push_back("");
        for (int j = 0; j < sizer[i]; j++)
        {
            string so;
            cin >> so;
            a[i].push_back(so);
        }
    }
    string f = T;
    memset(dp, mod, sizeof(dp));
    for (int i = 0; i <= maxn; i++)
    {
        dp[i][0] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= f.size(); j++)
        {
            dp[i][j] = dp[i - 1][j];
            for (int k = 0; k < a[i - 1].size(); k++)
            {
                int length = a[i - 1][k].size();
                if (length > j)
                    continue;
                bool tag = 1;
                for (int p = j - length, q = 0; p < j; p++, q++)
                {
                    if (f[p] != a[i - 1][k][q])
                    {
                        tag = 0;
                        break;
                    }
                }
                if (tag)
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - length] + 1);
            }
        }
    }
    if (dp[n][f.size()] <= n)
    {
        cout << dp[n][f.size()] << endl;
    }
    else
        cout << -1 << endl;
    system("pause");
    return 0;
}

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int mod = 998244353;
const int maxn = 201;
using p = pair<int, int>;
string T;
int n;
vector<int> sizer(101);
vector<string> a[1001];
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr)
int dp[maxn];
int g[maxn];
int main()
{
    IOS;
    cin >> T;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> sizer[i];
        // a[i].push_back("");
        for (int j = 0; j < sizer[i]; j++)
        {
            string so;
            cin >> so;
            a[i].push_back(so);
        }
    }
    string f = T;
    memset(dp, mod, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= f.size(); j++)
        {
            g[j] = dp[j];
            for (int k = 0; k < a[i - 1].size(); k++)
            {
                int length = a[i - 1][k].size();
                if (length > j)
                    continue;
                bool tag = 1;
                for (int p = j - length, q = 0; p < j; p++, q++)
                {
                    if (f[p] != a[i - 1][k][q])
                    {
                        tag = 0;
                        break;
                    }
                }
                if (tag)
                    g[j] = min(g[j], dp[j - length] + 1);
            }
        }
        swap(dp,g);
    }
    if (dp[f.size()] <= n)
    {
        cout << dp[f.size()] << endl;
    }
    else
        cout << -1 << endl;
    system("pause");
    return 0;
}

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=998244353;
const int INF=1e18;
using p=pair<int,int>;
#define endl "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#undef int
int main()
{
  #define int long long
    IOS;
    list<int>l;
    map<int,list<int>::iterator>mp;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        l.push_back(a);
        mp[a]=--l.end();
    }
    int q;
    cin>>q;
    for(int j=1;j<=q;j++)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int x,y;
            cin>>x>>y;
            auto it=mp[x];
            it++;
            l.emplace(it,y);
            mp[y]=--it;
        }
        else
        {
            int x;
            cin>>x;
            l.erase(mp[x]);
        }
    }
    for(auto p:l)
    {
        cout<<p<<" ";
    }
    cout<<endl;
    system("pause");
    return 0;

}

去掉要求如何贪心？

什么时候出现反悔行为？满足什么条件才能反悔？反悔时的操作是什么？

反悔时肯定是选中间的没有选择两边的思想更优，所以在取一个点的时候将它左右两边的点与中间作差的结果记入该点并更新其左右邻居信息为反悔备选点的左右邻居端点进行维护，此时就可以把反悔点视作新的结点操作了。

来自_

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 100;
struct node{
    int id,w;
    node(){
        id=w=0;
    }
    node(int x, int y){
        id=x,w=y;
    }
    bool operator<(const node &x) const{
        return w<x.w;
    }
};
int n,k,a[N],l[N],r[N];
bool vis[N];
priority_queue<node> q;
typedef long long ll;
ll ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        l[i]=i-1,r[i]=i+1;
        q.push(node(i,a[i]));
    }
    for(int i=1;i<=k;i++){
        while(vis[q.top().id])q.pop();
        node now=q.top();
        if(now.w<0)break;
        q.pop();
        ans+=now.w;
        a[now.id]=now.w=a[l[now.id]]+a[r[now.id]]-a[now.id];
        q.push(now);
        vis[l[now.id]]=vis[r[now.id]]=1;
        l[now.id]=l[l[now.id]],r[now.id]=r[r[now.id]];
        l[r[now.id]]=r[l[now.id]]=now.id;
    }
    cout<<ans<<'\n';
    
}