分类 HDU 下的文章

Taotao Picks Apples

题目连接

[HDU 6406] 2018 Multi-University Training Contest 8--1010 Taotao Picks Apples

题解

高档题。题意大概是给定一组数字,按照如下规则以此取数:

  • 取出第一个数
  • 如果当前数字严格大于上一个选取的数字,取出当前数字

现在给出多个询问,每个询问处理将某个数字改成其他数字,求取出多少数字。

首先将原序列中取出的数字找出来,标记为关键点,之后将两两关键点之间以上一个关键点作为第一个取出的数字,找出区间内可以取到的关键点。接下来分为以下几种情况讨论

  • 修改的数字为第一组关键点

    • 将当前数字升高
      直接判断第一批关键点中严格大于修改后数字的第一个数字,输出原始序列答案减去两数之间的关键点数即可。
    • 将当前数字降低
      首先判断修改后数字的值是否严格大于上一个关键点。如果不是,将答案记录为原数字减一,之后再将答案加上该位置对应的第二组关键点中大于修改后数字的数量。
  • 修改的数字不是第一组关键点

    • 将当前数字升高

      • 修改后的值小于等于上一个第一组关键点
        直接输出原始序列的答案
      • 修改后的值大于上一个第一组关键点
        判断第一批关键点中严格大于当前位置值最小的一个,原始序列答案减去两数之间关键点数即为答案。
    • 将当前数字降低
      直接输出原始序列的答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int input[maxn];
int imp[maxn],pos[maxn];
int isimp[maxn];
vector<int> decc[maxn];
int main(){
//    freopen("1.in","r",stdin);
//    freopen("zj.out","w",stdout);
//    ios::sync_with_stdio(0);
//    cout.tie(0);
//    cin.tie(0);
    int t,n,m,pre,num,p,q;

    for (cin>>t;t;t--){
        memset(isimp,0,sizeof(isimp));
        memset(imp,0,sizeof(imp));
        memset(pos,0,sizeof(pos));
        num=0;

        cin>>n>>m;
        for(int i=1;i<=n;i++)decc[i].clear();
        for (int i=1;i<=n;i++){
            scanf("%d",&input[i]);
        }

        pre=input[1];
        imp[++num]=input[1];
        pos[num]=1;
        isimp[num]=1;
        for (int i=2;i<=n;i++){
            if(input[i]>pre){
                pre=input[i];
                imp[++num]=input[i];
                pos[num]=i;
                isimp[i]=num;
            }
        }
        for (int i=1;i<num;i++){
            pre=imp[i-1];
            for (int j=pos[i]+1;j<pos[i+1];j++){
                if (input[j]>pre){
                    pre=input[j];
                    decc[i].push_back(pre);
                }
            }
        }
        pre=imp[num-1];
        for (int j=pos[num]+1;j<=n;j++){
            if (input[j]>pre){
                pre=input[j];
                decc[num].push_back(pre);
            }
        }

        for (int i=1;i<=m;i++){
            cin>>p>>q;
            if (isimp[p]){
                if (q==input[p]){
                    //cout<<num<<endl;
                    printf("%d\n",num);
                }
                else if (q>input[p]){
                    int temp=(int)(upper_bound(imp+1,imp+num+1,q)-imp);
                    printf("%d\n",isimp[p]+num-temp+1);
                    //cout<<isimp[p]+num-temp+1<<endl;
                }
                else if(q<input[p]){
                    int temp=(int)(upper_bound(decc[isimp[p]].begin(),decc[isimp[p]].end(),q)-decc[isimp[p]].begin());
                    //cout<<num-(q>imp[isimp[p]-1]?0:1)+decc[isimp[p]].size()-temp<<endl;
                    printf("%d\n",num-(q>imp[isimp[p]-1]?0:1)+decc[isimp[p]].size()-temp);
                }
            }
            else{
                int temp=(int)(upper_bound(pos+1,pos+num+1,p)-pos);
                temp--;
                if (q<=imp[temp])printf("%d\n",num);
                else{
                    int temp1=(int)(upper_bound(imp+1,imp+num+1,q)-imp);
                    //cout<<temp+num-temp1+1+1<<endl;
                    printf("%d\n",temp+num-temp1+1+1);
                }

            }
        }
    }
}

Magic Square

题目链接

[[HDU 6401] 2018 Multi-University Training Contest 8--1005 Magic Square](http://acm.hdu.edu.cn/showproblem.php?pid=6401]

题解

简单题。题意大概是给定一个矩阵,要求你做出一些旋转操作后输出矩阵。
签到题,直接输出即可。

代码

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
typedef pair<int,int>P;
const int maxn=1e5+50;
string s[5];
string temp;
void zhuanc(char&lt,char&rt,char&ld,char&rd){
    char temp;
    temp=lt;
    lt=ld;
    ld=rd;
    rd=rt;
    rt=temp;
}
void zhuanr(char&lt,char&rt,char&ld,char&rd){
    char temp;
    temp=lt;
    lt=rt;
    rt=rd;
    rd=ld;
    ld=temp;
}
int main() {
    int n,t;
    for (cin>>t;t;t--){
        cin>>n;
        for (int i=0;i<=2;i++){
            cin>>s[i];
        }
        for (int i=1;i<=n;i++){
            cin>>temp;
            if (temp[0]=='1'){
                temp[1]=='C'?zhuanc(s[0][0],s[0][1],s[1][0],s[1][1]):zhuanr(s[0][0],s[0][1],s[1][0],s[1][1]);
            }
            else if (temp[0]=='2'){
                temp[1]=='C'?zhuanc(s[0][1],s[0][2],s[1][1],s[1][2]):zhuanr(s[0][1],s[0][2],s[1][1],s[1][2]);
            }
            else if (temp[0]=='3'){
                temp[1]=='C'?zhuanc(s[1][0],s[1][1],s[2][0],s[2][1]):zhuanr(s[1][0],s[1][1],s[2][0],s[2][1]);
            }
            if (temp[0]=='4'){
                temp[1]=='C'?zhuanc(s[1][1],s[1][2],s[2][1],s[2][2]):zhuanr(s[1][1],s[1][2],s[2][1],s[2][2]);
            }
        }
        for (int i=0;i<=2;i++){
            cout<<s[i]<<'\n';
        }

    }
    return 0;
}

Parentheses Matrix

题目连接

[HDU 6440] 2018 Multi-University Training Contest 8--1004 Parentheses Matrix

题解

中档题,结论题。题意大概是构造一个h行w列的矩阵由'(',')'组成,使得每行每列所组成的匹配的括号串数最大。

首先考虑行或列为奇数的情况,显然任意一个匹配的字符串其长度必然为偶数,所以我们只要考虑为偶数的那一侧即可。
当行或列均为偶数时,首先我们必然可以保证行或列单独一个完全符合匹配。具体如下

((((((
))))))
((((((
))))))

在此基础之上可以稍加改进使得另一侧有(n-2)/2的数量可以获得匹配,具体如下

((((((
()()()
)()()(
))))))

之后可以发现,若要使得第一行匹配,至多只可能有一半的列匹配,第一列匹配的情况同理。所以我们首相将第一行列与最后一行列稍加改进,具体如下

((((((
(....)
(....)
))))))

在此基础之上将中间空白部分交替排列即可做到行数+列数-4的匹配数量,具体如下:

((((((
(()())
()()()
))))))

当数据较小时这种匹配方式可能未必比前几种更优秀,但当数据量增大时显著比前几种更优。

代码

#include <bits/stdc++.h>

using namespace std;
char output[205][205];
int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t;
    for (cin >> t; t; t--) {
        int h,w;
        cin >> h >> w;
        if (h % 2) {
            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) {
                    putchar((j) % 2 ? '(' : ')');
                }
                putchar('\n');
            }
        } else
            if (w % 2) {
                for (int i = 1; i <= h; i++) {
                    for (int j = 1; j <= w; j++) {
                        putchar((i) % 2 ? '(' : ')');
                    }
                    putchar('\n');
                }
            } else {
                if (max(h,w)+(min(h,w)-2)/2>=h+w-4){
                if (h >= w) {
                    for (int i=1;i<=h;i++){
                        output[i][1]='(';
                        output[i][w]=')';
                    }
                    for (int i=1;i<=h;i++){
                        for (int j=2;j<=w-1;j++){
                            output[i][j]=(i+j)%2?'(':')';
                        }
                    }
                }
                else {
                    for (int i=1;i<=w;i++){
                        output[1][i]='(';
                        output[h][i]=')';
                    }
                    for (int i=2;i<=h-1;i++){
                        for (int j=1;j<=w;j++){
                            output[i][j]=(i+j)%2?'(':')';
                        }
                    }
                }
                for (int i=1;i<=h;i++){
                    for (int j=1;j<=w;j++){
                        putchar(output[i][j]);
                    }
                    putchar('\n');
                }}
                else {
                    for (int i=1;i<=h;i++){
                        for (int j=1;j<=w;j++){
                            if (i==1||j==1)output[i][j]='(';
                            else if (i==h||j==w)output[i][j]=')';
                            else output[i][j]=(i+j)%2?')':'(';
                        }
                    }
                    for (int i=1;i<=h;i++) {
                        for (int j = 1; j <= w; j++) {
                            putchar(output[i][j]);
                        }
                        putchar('\n');
                    }
                }
            }
    }
}

Swordsman

题目连接

[HDU 6396] 2018 Multi-University Training Contest 7--1011 Swordsman

题解

中档题,提议大概是某人是一个剑士要打怪。剑士和怪物均有不同的属性,只有当剑士的所有属性均不低于怪物的对应属性时剑士才可以将怪物干掉。击杀怪物将获得一定的经验值,具体表现为每一种属性均可以获得怪物该属性经验值所对应的增长。求剑士最多可以击杀的怪物数量以及击杀之后的各项属性值。

首先注意到至多只有五项属性。我们将怪物的每个属性单独进行排序。之后重复以下过程:将当前属性小于剑士的怪物计数加一,将所有计数达到属性数量的怪物击毙并基于勇者经验值。直到所有怪物均被击杀或者无法击杀新的怪物。总的时间复杂度为O(knlogn+nk)。

注意需要使用读入挂,不然绝对会超时。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*fronthead,*fronttail;
inline char GET_CHAR(){
    if(fronthead==fronttail){
        int l=fread(buffer,1,BufferSize,stdin);
        fronttail=(fronthead=buffer)+l;
        if(fronthead==fronttail)return EOF;
    }
    return *fronthead++;
}
inline int READ(){
    int x=0,f=1;char c=GET_CHAR();
    for(;!isdigit(c);c=GET_CHAR()){
        if(c==EOF)return EOF;
        if(c=='-')f=-1;
    }
    for(;isdigit(c);c=GET_CHAR())x=(((x<<2)+x)<<1)+c-'0';
    return x*f;
}
const int maxn = 100005;
const int INF = 2147483647;
int n,k,q1;
int v[6],pos[6];
int b[maxn][6];
int num[maxn];
pair<int,int> sorta[6][maxn];
int ans;
inline void read() {
    ans=0;
    n=READ(),k=READ();
    for (int i=1;i<=k;i++){
        v[i]=READ();
        pos[i]=0;
        sorta[i][n+1].first=INF;
    }
    for (int i=1;i<=n;i++){
        num[i]=0;
        for (int j=1;j<=k;j++){
            sorta[j][i].first=READ();
            sorta[j][i].second=i;
        }
        for (int j=1;j<=k;j++){
            b[i][j]=READ();
        }
    }
    for (int i=1;i<=k;i++){
        sort(sorta[i]+1,sorta[i]+1+n);
    }
}

inline bool slove() {
    bool flag= true;
    while(flag){
        flag=false;
        for (int i=1;i<=k;i++){
            while(sorta[i][pos[i]+1].first<=v[i]){
                pos[i]++;
                num[q1=sorta[i][pos[i]].second]++;
                if (num[q1]==k){
                    ans++;
                    flag=true;
                    for (int j=1;j<=k;j++){
                        v[j]+=b[q1][j];
                    }
                }
            }
        }
    }
}

int _;
int main() {
    _=READ();
    while (_--) {
        read();
        slove();
        printf("%d\n",ans);
        for (int i=1;i<=k;i++){
            printf("%d%c",v[i],(i==k?'\n':' '));
        }
    }
    return 0;
}

Robotic Sort

题目链接

[HDU 1890] Robotic Sort

题解

高档题。题意大概是每次将一段连续的区间翻转,使得最后的序列有序,输出翻转过程。
Splay模板题,直接套即可。

代码

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

const int INF = 1 << 30;
const int maxn = 100005;

int order[maxn], input[maxn], siz[maxn], ch[maxn][2], rev[maxn], pre[maxn], id[maxn];
int root, top, n, r, ans;

bool cmp(int a, int b) {
    if (input[a] != input[b])
        return input[a]<input[b];
    return a<b;
}

inline void insert(int &x, int p) {
    x = ++top;
    siz[x] = 1;
    ch[x][0] = ch[x][1] = 0;
    pre[x] = p;
    rev[x] = 0;
}

inline void pushup(int x) {
    siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}

inline void pushdown(int x) {
    if (rev[x]) {
        swap(ch[x][0], ch[x][1]);
        rev[ch[x][0]] ^= 1;
        rev[ch[x][1]] ^= 1;
        rev[x] = 0;
    }
}

inline void build(int &x, int l, int r, int p) {
    int mid = (l + r) >> 1;
    insert(x, p);
    id[mid] = top;
    if (l<mid) build(ch[x][0], l, mid - 1, x);
    if (r>mid) build(ch[x][1], mid + 1, r, x);
    pushup(x);
}

inline void rotate(int x, int kind) {
    int y = pre[x];
    pushdown(y);
    pushdown(x);
    ch[y][!kind] = ch[x][kind];
    pre[ch[x][kind]] = y;
    if (pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x;
    pre[x] = pre[y];
    ch[x][kind] = y;
    pre[y] = x;
    pushup(y);
}

inline void splay(int x, int goal)
{
    while (pre[x] != goal) {
        if (pre[pre[x]] == goal) {
            pushdown(pre[x]);
            pushdown(x);
            rotate(x, ch[pre[x]][0] == x);
        }
        else {
            pushdown(pre[pre[x]]);
            pushdown(pre[x]);
            pushdown(x);
            int y = pre[x];
            int kind = ch[pre[y]][0] == y;
            if (ch[y][kind] == x) {
                rotate(x, !kind);
                rotate(x, kind);
            }
            else {
                rotate(y, kind);
                rotate(x, kind);
            }
        }
    }
    pushup(x);
    if (goal == 0) root = x;
}

inline void findLeft(int x) {
    pushdown(x);
    siz[x]--;
    if (ch[x][1] == 0) {
        int kind = ch[pre[x]][1] == x;
        pre[ch[x][0]] = pre[x];
        ch[pre[x]][kind] = ch[x][0];
        ch[x][0] = ch[root][0];
        ch[x][1] = ch[root][1];
        pre[ch[x][0]] = pre[ch[x][1]] = x;
        pre[x] = 0;
        root = x;
        pushup(x);
    }
    else findLeft(ch[x][1]);
}

inline int update(int r)
{
    splay(r, 0);
    int ans = siz[ch[r][0]] + 1;
    rev[ch[r][0]] ^= 1;
    if (ch[r][0] == 0) {
        ch[0][1] = ch[r][1];
        pre[ch[r][1]] = 0;
    }
    else findLeft(ch[r][0]);
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (cin >> n; n; cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> input[i];
            order[i] = i;
        }
        root = 1;
        top = 0;
        siz[0] = ch[0][0] = ch[0][1] = pre[0] = rev[0] = 0;
        build(ch[0][1], 0, n - 1, 0);

        sort(order, order + n, cmp);
        for (int i = 0; i<n; i++) {
            r = id[order[i]];
            ans;
            ans = update(r);
            printf("%d%c", ans + i, ((i == n - 1) ? '\n' : ' '));
        }
    }
}