HRBU

目录

A - Casimir's String Solitaire

题意：

做法：

B - Shifting Sort

题意：

做法：

C - Ticks

题意：

做法：

D - Productive Meeting

题意：

做法：

E - Permutation Minimization by Deque

做法：

F - Array Optimization by Deque

题意：

思路:

题意：

给定一个字符串，要求能把这个字符串消除完，消除规则为：1、你可以消除任意位置的一个A和一个B。2、你可以消除任意位置的一个B和一个C，问给定的字符串能不能消除完。

做法：

没有限制位置，那么只需要去统计A,B,C三个的个数是否满足A+C==B即可。

#include
typedef long long ll;
using namespace std;
int t,n,m,k;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        int A=0,B=0,C=0;
        cin>>s;
        for(int i=0;i 
B - Shifting Sort 
题意： 
给定你一个数组，要求把这个数组进行由小到大排序，你可以在数组内部划定一个区间，在这个区间内你可以进行左移操作，例如：[5,3,2,4,1]，我将[2,4]这个区间进行左移2位的操作，原数组就变成了[5,4,3,2,1]，要求你在n步操作内，将数组排序，并且输出你的每一步操作。
 
做法： 
题目说明答案不唯一，所以样例输出的仅供参考，n步内排序，我们有很多种方法，但是设计下标调整的，最简单的就是冒泡排序（碰到大的就移到最后，最多n步，就可以将数组排序完成）了，我们可以将原数组重新记录一个数组，并将这个数组进行排序，然后两个数组相比较，之后比较下标是否相同，不同就对原数组进行移动操作，保持数组永远是一个动态，n只有50所以时间复杂度完全ok
 
#include
typedef long long ll;
using namespace std;
const int maxn=60;
int t,n,m,k;
string s;
struct Node
{
    int l,r,pos;
}ans[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n;
        int a[maxn],b[maxn],temp[maxn];
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        int cnt=0;
        for(int i=n;i>=1;i--)
        {
            int k=0;
            for(int j=i;j>=1;j--)
            {
                if(a[j]==b[i])
                {
                    k=j;
                    break;
                }
            }
            if(k!=0&&k!=i)
            {
                ans[++cnt]={k,i,1};
                for(int i=1;i<=k-1;i++)
                    temp[i]=a[i];
                for(int i=k;i<=n-1;i++)
                    temp[i]=a[i+1];
                temp[n]=a[k];
                memcpy(a,temp,sizeof(temp));
            }
        }
        cout< 
C - Ticks 
题意： 
给定一个图，这张图由*以及" "组成，要去你去判断这张图上所有的*是否都可以组成"V"这个样子，且长度要大于k
 
做法： 
标标准准的模拟，当时居然卡了一个小时，我是fw！只需要在第一遍遍历地图时，对于每一个*组成的"V"字样进行判断，判断两个：1、这个位置的下标是否已经越界了。2、这个位置在原地图上是否还是*。判断完一个比较一下长度，因为"V"的左右边长度不一定等长（地图限制），所以两者取小和k比较，要是小于k就不考虑了，若是大于则把这个"V"包含的位置都标记上，最后再跑一遍地图，发现有*的位置还未标记直接输出No。
 
#include
typedef long long ll;
using namespace std;
int t,n,m,k;
char mp[25][25];
bool vis[25][25];
bool judge(int a,int b)
{
    if(a<=0||a>n||b<=0||b>m)
        return 0;
    return 1;
}
void slove(int x,int y)
{
    int l=0,r=0;
    while(judge(x-l,y-l)&&mp[x-l][y-l]=='*')
        l++;
    while(judge(x-r,y+r)&&mp[x-r][y+r]=='*')
        r++;
    l--,r--;
    if(min(l,r)>=k)
    {
        for(int i=0;i<=min(l,r);i++)
        {
            vis[x-i][y-i]=true;
            vis[x-i][y+i]=true;
        }
    }

}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        int flag=1;
        memset(vis,false,sizeof(vis));
        cin>>n>>m>>k;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                cin>>mp[i][j];
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(mp[i][j]=='*')
                {
                    slove(i,j);
                }
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(mp[i][j]=='*'&&!vis[i][j])
                {
                    flag=0;
                }
            }
        }
        if(!flag)
            cout<<"NO"< 
D - Productive Meeting 
题意： 
给定一个数组，第i位表示这第i个人有a[i]次交谈机会，每交谈一次a[i]--，当a[i]=0时，第i个人退出会议，问当会议中只剩下一个人时，前面都是哪几个人在对话？
 
做法： 
最后剩下一个人，那么这个人只能是之前数组里的最大值，那么我们只需要每一次都去找值最大的两个人，把他们的次数都-1，然后判断是否为0，不为0就继续进入，继续循环，优先队列去前两位就行，用pair存坐标以及对应的值。
 
#include
#define pii pair
typedef long long ll;
using namespace std;
const int maxn=2e5+10;
int t,n,m,k;
char mp[25][25];
bool vis[25][25];
int x;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--)
    {
        priority_queue q;
        vector ans;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            if(x!=0)
                q.push({x,i});
        }
        while(q.size()>1)
        {
            auto tmp1=q.top();
            //cout<0)
                q.push({tmp1.first-1,tmp1.second});
            if(tmp2.first-1>0)
                q.push({tmp2.first-1,tmp2.second});
        }
        while(!q.empty())
            q.pop();
        cout<
 
E - Permutation Minimization by Deque 
做法： 
模拟双端队列deque，模拟就完了！
 
#include
typedef long long ll;
using namespace std;
const int maxn=2e5+10;
int t,n,m,k;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        int p[maxn],ans[maxn];
        deque dq;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>p[i];
        dq.push_front(p[1]);
        for(int i=2;i<=n;i++)
        {
            if(p[i]>dq.front())
                dq.push_back(p[i]);
            else
                dq.push_front(p[i]);
        }
        int k=0;
        while(!dq.empty())
        {
            ans[k++]=dq.front();
            dq.pop_front();
        }
        cout<
 
F - Array Optimization by Deque 
题意： 
还是双端队列，但是这次需要判断的是最小的反转数个数，什么叫反转数，根据题目来看就是a[i]>a[j]且i
 
思路: 
然而我理解错了，题目要求算的是每一个数的代价，如果一个数放前面，代价是后面所有比它小的数的个数，如果一个数放后面，代价是前面所有比它大的数的个数（转载于：Codeforces Round #744 (Div. 3) A-F 题解 - 知乎）大佬们都说用树状数组维护就行，咱也不会啊，只能QAQ了