倒数排列

思路

令给出的排列是，则答案，可以通过样例和直觉猜出来。

参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n ; scanf("%d",&n) ;
    for(int i = 1;i <= n;i++) {
        int x ; scanf("%d",&x) ;
        printf("%d ",n - x + 1) ;
    }
    return 0;
}

小易的英语软件

思路

有多种不同的做法。这里介绍一种比较好理解的：桶排+前缀和。
分数只有 种，考虑对于每一种分数开一个桶 ，表示分数等于 的人数，输入的时候就可以搞定。
现在分数不超过 的人数，就是求：
这个用前缀和可以快速求出。
最后要求输出百分数，这个在纸上推一下就好了。

参考代码

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 10000;

int n, m;
int a[MAXN+1];
int buc[151], pre[151];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        ++buc[ a[i] ];
    }
    pre[0] = buc[0];
    for (int i = 1; i <= 150; ++i)
        pre[i] = pre[i - 1] + buc[i];
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        int x;
        scanf("%d", &x);
        double ans = 100.0 * (pre[ a[x] ] - 1) / n;
        printf("%.6lf\n", ans);
    }

    return 0;
}

最大公约数

思路

，这是欧几里得算法。那我们只要实现的计算。 可以直接在输入的时候维护（详见代码）。

参考代码

#include<bits/stdc++.h>
using namespace std;
char s[100005];
long long gcd(long long a,long long b)
{
    return a % b == 0 ?b : gcd(b , a % b) ;
}
int main()
{
    scanf("%s",s+1) ;
    long long a ; cin >> a;
    long long b = 0;
    for(int i = 1;s[i] != '\0';i++) {
        b = (b * 10 + s[i] - '0') % a;
    }
    cout << gcd(b , a) ;
    return 0;
}

按位或

思路

对于每一次询问，我们肯定会选择所有，满足，即在二进制表达下，是的子集。
那么我们可以维护一个数组]，表示所有为的子集的数字的Or值是多少。每次插入一个数字，如果它没有重复出现过，就枚举它的超集更新答案。询问的时候只需要看是否等于就好了。

参考代码

#include<bits/stdc++.h>
using namespace std;
int p[131072] ;
int mx = 131071 ;
int q ;
int main()
{
    scanf("%d",&q) ;
    while(q--) {
        int op , x;scanf("%d%d",&op,&x) ;
        if(op == 1) {
            if(p[x] == x) continue ;
            int s = mx ^ x;
            for(int i = s ; i ; i = (i - 1) & s) {
                p[i ^ x] |= x ;
            }
            p[x] = x;
        }
        else {
            if(p[x] == x) puts("YES") ;
            else puts("NO");
        }
    }
    return 0;
}

放置货物

思路

枚举货物放置的左上角，剩下的只需要检查某个矩形里面有没有障碍物。 把障碍物看成1，空格看成0，维护二维前缀和，就可以快速查询矩形和。如果矩形和是0则可以放置。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n , m , k;
int a[1005][1005];
int c , d;
void solve()
{
    scanf("%d%d%d",&n,&m,&k);memset(a , 0 , sizeof(a)) ;
    for(int i = 1;i <= k;i++) {
        int x , y;scanf("%d%d",&x,&y);
        a[x][y] = 1;
    }
    scanf("%d%d",&c,&d);
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1] ;
        }
    }
    for(int i = 1;i <= n - c + 1 ; i ++) {
        for(int j = 1;j <= m - d + 1 ; j++) {
            int s = a[i+c-1][j+d-1] - a[i-1][j+d-1] - a[i+c-1][j-1] + a[i-1][j-1] ;
            if(!s) {
                puts("YES") ;return ;
            }
        }
    }
    puts("NO") ; return ;
}
int main()
{
    int t ;scanf("%d",&t) ;
    while(t--) solve();
}

最大最小值

思路

首先注意到答案按顺序不减。
考虑把数字从大到小插入，当前插入数字u，那么假设某个k满足ans[k] <= u，则u和u之前的数字把序列分成了一段段，k要满足k <= 这些段中最长的。这样处理完毕之后再填入处理过程中没有填的位置。

参考代码

#include<bits/stdc++.h>
using namespace std;
multiset<int> st ;
int n , k;
struct num
{
    int v ;
    int id;
}h[100005];
bool cmp(num a,num b)
{
    return a.v < b.v;
}
int L[100005] , R[100005];
int ans[100005];
int main()
{
    scanf("%d",&n) ;
    for(int i = 1;i <= n;i++) {
        scanf("%d",&h[i].v) ;
        h[i].id = i;
    }
    sort(h + 1 , h + n + 1, cmp) ;
    for(int i = 1;i <= n;i++) {
        L[i] = i - 1,R[i] = i + 1; ans[i] = 2e9;
    }
    for(int i = 1;i <= n;i++) {
        int a = h[i].id - L[h[i].id] - 1 , b = R[h[i].id] - h[i].id - 1 ;
        if(a) st.erase(st.find(a));
        if(b) st.erase(st.find(b)) ;
        st.insert(a + b + 1) ;
        L[R[h[i].id]] = L[h[i].id] ; R[L[h[i].id]] = R[h[i].id] ;
        multiset<int>::iterator it = st.end() ; it--;
        ans[*it] = min(ans[*it] , h[i].v) ;
    }
    for(int i = n ; i >= 1;i--){
        if(ans[i] == (2e9)) ans[i] = ans[i + 1];
    }
    for(int i = 1;i <= n;i++) printf("%d ",ans[i]) ;
    return 0;
}

序列交换

思路

只要数组中同时出现了奇数和偶数，那么直接对数组进行排序即可。

参考代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>

const int N = 1e5 + 10;

int a[N];

using namespace std;
int main()
{
    int n;
    cin >> n;
    int odd = 0,even = 0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]%2==0)
            even++;
        else
            odd++;
    }
    if(even>0 && odd>0)
        sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

数字圆环

思路

首先对数组进行排序，除了最后一个数字，都满足相邻两个数字大于自己
对于最后一个数字，交换最后两个数字，判断是否满足条件即可。

参考代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        for (int i = 0;i < n;i++) scanf("%d",&a[i]);
        sort(a,a+n);
        swap(a[n-2],a[n-1]);
        bool f = 0;
        for (int i = 0;i < n;i++)
        {
            int pre = (i-1+n)%n;
            int sub = (i+1) % n;
            if (a[pre] + a[sub] <= a[i]) f = 1;
        }
        if (f) puts("NO");
        else
        {
            puts("YES");
        }
    }
    return 0;
}

优秀的01序列

思路

我们对序列不断执行rev操作，得到的一系列序列。再依次翻转每个序列的每一位，得到一系列序列

例如"110011"可以生成{"110011","1100","11"}与{"001100","0011","00"}

如果是优秀的，当且仅当是由这两组序列拼接而成，并且第一组序列中最原始的序列不能接第二组序列中的序列。

可以使用dp来维护上述过程。令f[i][0/1]表示前i位是否优秀，且拼接的最后一个01串是不是初始序列。按定义转移即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
char s[1005] , t[1005];
int h[1005];
const int base = 773117 , mod = 1e9 + 7;
int pr[1005];
int s1[1005] , s2[1005] , len;
int pos[1005];
int n , m;
int ghash(int l,int r)
{
    return ((h[r] - 1LL*h[l-1]*pr[r-l+1]) % mod + mod ) % mod;
}
int dp[1005][2];
void solve()
{
    scanf("%s",s+1);
    scanf("%s",t+1);
    n = strlen(s + 1) , m = strlen(t + 1) ;
    for(int i = 1;i <= m;i++) h[i] = (1LL * h[i - 1] * base + t[i] - '0') % mod;
    int pc = 0;len = 0;
    for(int i = 1;i <= n;i++) {
        if(s[i] != s[i - 1]) {
            int h1 = 0 , h2 = 0;
            for(int j = i;j <= n;j++) {
                h1 = (1LL * h1 * base + s[j] - '0') %mod;
                h2 = (1LL * h2 * base + 1 + '0' - s[j]) % mod;
            }
            if(!pc) {
                ++len ; s1[len] = h1 ; s2[len] = h2;
            }
            else {
                ++len ; s1[len] = h2 ; s2[len] = h1 ;
            }
            pos[len] = (n - i + 1) ;
            pc ^= 1;
        }
    }
    memset(dp , 0 , sizeof(dp)) ; dp[0][1] = 1;
    for(int i = 1;i <= m;i++) {
        if(i >= pos[1] && ghash(i - pos[1] + 1 , i) == s1[1] && (dp[i - pos[1]][0] || dp[i - pos[1]][1])) dp[i][1] = 1;
        for(int j = 2;j <= len;j++) {
            if(i >= pos[j] && ghash(i - pos[j] + 1 , i) == s1[j] && (dp[i - pos[j]][0] || dp[i - pos[j]][1])) {dp[i][0] = 1;break;}
        }
        for(int j = 1;j <= len;j++) {
            if(i >= pos[j] && ghash(i - pos[j] + 1 , i) == s2[j] && dp[i - pos[j]][0]) {dp[i][0] = 1;break;}
        }
    }
    if(dp[m][0] || dp[m][1]) puts("YES");
    else puts("NO");
    return ;
}
int main()
{
    int t;scanf("%d",&t) ;
    pr[0] = 1;
    for(int i = 1;i <= 1000;i++) pr[i] = 1LL * pr[i - 1] * base % mod;
    while(t--) solve() ;
    return 0;
}

序列维护

思路

注意到如果，那么不管怎么操作都有。
于是把数字从小到大排序后，每次询问就二分出对应的位置，并把后面的数字全部减一。具体实现可以用树状数组或者更高级的数据结构。

参考代码

#include<bits/stdc++.h>
using namespace std;
int c[200005];
int n , q;
inline int lowbit(int x)
{
    return x & (-x) ;
}
void add(int x)
{
    while(x <= n) {
        c[x]++ ; x += lowbit(x) ;
    }
}
int query(int x)
{
    int ans = 0;
    while(x) {
        ans += c[x] ; x -= lowbit(x) ;
    }
    return ans;
}
int a[200005];
int main()
{
    scanf("%d%d",&n,&q) ;
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]) ;
    sort(a + 1 , a + n + 1) ;
    while(q--) {
        int x ; scanf("%d",&x) ;
        if(x > a[n] - query(n)) {puts("0");continue ;}
        int l = 1 , r = n;
        while(l < r) {
            int mid = (l + r >> 1) ;
            if(a[mid] - query(mid) >= x) r = mid ;
            else l = mid + 1;
        }
        printf("%d\n",n - l + 1) ;
        add(l) ;
    }
    return 0;
}