A. Strange Table

题意

给你一个以行为顺序的依次递增的矩阵,然后问你以列为顺序的第X个元素的值是多少

解题思路

很明显新的列数等于\left \lceil \frac{x}{n} \right \rceil ,新的行数等于X % n,注意的是,这里取模如果等于0的话,表示的是最后一行

Code

#include
using namespace std;
#define ll long long
int main()
{
    ll t,n,m,x;
    scanf("%lld",&t);
    while(t--) {
        scanf("%lld%lld%lld",&n,&m,&x);
        ll hang = x % n;
        if(!hang) hang = n;
        ll lie = (long long)ceil(x*1.0/n);
//      printf("hang = %d,lie = %d\n",hang,lie);
        printf("%lld\n",(hang - 1)*m+lie);
    }

}

B. Partial Replacement

题意

给你一个长度为n的字符串,然后再满足首尾*都为X的情况下的问你最少需要多少X使得所有相邻X的距离都小于k

解题思路

在保证了首尾都为X的情况下,我们贪心的选取字符的间距,然后如果此字符的后面第K个字符不是*,那么我们就往回找 *,这样就能找到最少的更换次数了

Code

#include
#include
#include
#include
#include
#include
using namespace std;
#define mt(x) memset(x,0,sizeof x)
#define N 2021 
typedef long long ll;
char s[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k,ans=2;
        scanf("%d %d",&n,&k);
        scanf("%s",s);
        int p=0,q=strlen(s)-1,l=q+1;
        while(s[p]!='*'&&s[p])p++;
        while(s[q]!='*'&&s[q])q--;
        s[p]='x';
        s[q]='x';
        if(p!=q)
        {
            int i=p+k;
            while(i

C. Double-ended Strings

题意

给你两个字符串,你每次能对其中一个字符串前面的字母或者后面的字母进行删除,问你最少需要几次删除操作使得两个字符串相等

解题思路

我们直接暴力匹配两个字符串的最长子串长度,然后用两个字符串的总长度减去2*相等子串的长度

Code

#include
#include
#include
#include
#include
#include
using namespace std;
#define mt(x) memset(x,0,sizeof x)
#define N 2021
int nt[N];
char x[N],y[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",x);
        scanf("%s",y);
        int lx=strlen(x);
        int ly=strlen(y);
        int mx=0,ans=0;
        for(int i=0;i

D. Epic Transformation

题意

给你一个长度为n的数组,你每次可以选择两个值不同的数,然后将这两个数从中删掉,问你最后最少还剩多少数字

解题思路

我们先对数组排序,然后将数组一分为二,我们让第一个区间的第一个数和第二个区间的相应位置的数进行匹配,发现不同的那么剩余长度-2,这样就能得到一个最后剩余最少的结果,注意的是这里的数组长度为奇数的时候,我们直接不用管最中间的那个元素,因为它必然不能被消掉

Code

#include
using namespace std;

int t,n;
const int N = 200005;
int a[N];

int main()
{
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i = 0;i < n; ++i) {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        int mid = (n) / 2;
        int ans = n;
        if(n%2==0) {
            for(int i = 0;i < mid; ++i) {
                if(a[i] != a[mid + i]) {
                    ans -= 2;
                }
            }
        }
        else {
            for(int i = 0;i < mid; ++i) {
                if(a[i] != a[mid + i + 1]) {
                    ans -= 2;
                }
            }
        }
        printf("%d\n",ans);
    }


    return 0;
}

E. Restoring the Permutation

题意

都做到这里了,题意就不说了

解题思路

对于minimal permutation :

我们先将1-n装进set里面,如果当前的q[i] > q[i-1],那么我们就要输出q[i],然后更删掉q[i]这个元素,否则我们输出set的第一个元素,然后删掉它

对于maximal permutation :

我们先将1-n装进set里面,如果当前的q[i] > q[i-1],那么我们就要输出q[i],然后更删掉q[i]这个元素,否则我们通过set的lower_bound找到小于q[i]的第一个元素

详情请看code

Code

#include
using namespace std;

const int N = 200005;
set S;
int a[N];

int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--) {
        S.clear();
        scanf("%d",&n);
        for(int i = 1;i <= n; ++i) {
            scanf("%d",&a[i]);
        }
        for(int i = 1;i <= n; ++i) {
            S.insert(i);
        }
        for(int i = 1;i <= n; ++i) {
            if(a[i] > a[i-1]) {
                printf("%d ",a[i]);
                S.erase(a[i]);
            }
            else {
                auto it = S.begin();
                printf("%d ",*it);
                S.erase(it);
            }
        }
        puts("");
        for(int i = 1;i <= n; ++i) {
            S.insert(i);
        }
        for(int i = 1;i <= n; ++i) {
            if(a[i] > a[i-1]) {
                printf("%d ",a[i]);
                S.erase(a[i]);
            }
            else {
                auto it = S.lower_bound(a[i]);
                it--;
                printf("%d ",*it);
                S.erase(it);
            }
        }
        puts("");
    }
    return 0;
}

最后

E题没做出来,当时的想法没往STL上面靠,然后一直T on test7,有点小遗憾


本当の声を響かせてよ