2018年5月

贝壳找房移山(简单/中等)

题目链接

贝壳找房移山(简单)
贝壳找房移山(中等)

题解

中档题。由于每次移山是将连续的一段山顶移除1个单位的高度,只需提取出所有的山顶与山谷的高度来减少运算量。
之后每次贪心找出并抹去一个消耗最少的山顶即可。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#define maxxx(a,b) (a>b?a:b)
#define ll long long
using namespace std;
ll n, k,t;
ll a;
vector<ll> high;
int main() {
    cin >> t;
    for (ll q = 1; q <= t; q++) {
        cin >> n >> k;
        ll last = 0, ans = 0;
        high.clear();
        bool which = true;//true 找峰,false找谷底
        high.push_back(0);
        for (ll i = 1; i <= n; i++) {
            cin >> a;
            if (which) {
                if (a < last) {
                    high.push_back(last);
                    which = false;
                }
            }
            else {
                if (a > last) {
                    high.push_back(last);
                    which = true;
                }
            }
            last = a;
        }
        if (which == true) {
            high.push_back(last);
            high.push_back(0);
        }
        else
            high.push_back(0);
        ll numofsf = high.size() / 2;
        for (ll i = 1; i <= numofsf-k; i++) {
            ll willdel = 1;
            for (ll j = 1; j <= high.size() / 2; j++) {
                if (high[j * 2 - 1] - (maxxx(high[j * 2 - 2], high[j * 2])) < high[willdel] - maxxx(high[willdel - 1], high[willdel + 1]))
                    willdel = j * 2 - 1;
            }
            if (high[willdel + 1] > high[willdel - 1]) {
                ans += high[willdel] - high[willdel + 1];
                high.erase(high.begin() + willdel);
                high.erase(high.begin() + willdel);
            }
            else {
                ans += high[willdel] - high[willdel - 1];
                high.erase(high.begin() + willdel-1);
                high.erase(high.begin() + willdel-1);
            }
        }
        cout << ans<<endl;
    }
}

题目链接

贝壳找房

题解

简单题。直接模拟即可。

代码

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int n, m;
int xuqiu[10005];
bool fc(int a, int b) {
    return a < b;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> m;
        for (int j = 1; j <= m; j++) {
            cin >> xuqiu[j];
        }
        sort(&xuqiu[1], &xuqiu[m + 1], fc);
        int a = 1;
        int num = 1;
        for (;a<xuqiu[1];) {
            a = a + num++ + 2;
        }
        if (a == xuqiu[1]) {
            bool boo = true;
            for (int j=1; j<=m;j++) {
                if (a != xuqiu[j]) {
                    boo = false;
                    break;
                }
                a = a + num++ + 2;
            }
            if (boo)cout << "yes" << endl;
            else cout << "no" << endl;
        }
        else cout << "no" << endl;
    }
}

贝壳找房算数(简单)

题目链接

贝壳找房算数(简单)

题解

简单题,因为数据规模不大,直接暴力运算即可

代码

#include <iostream>
#include <math.h>
using namespace std;
#define max___(a,b) (a>b?a:b)
#define min___(a,b) (a<b?a:b)
#define LL long long
#define maxll 1000000000000000
LL n, m,t,j,k;
LL a[10005];
long long gcd(long long x, long long y) {

    if (x>y)return gcd(y, x);
    if (x == 0)return y;
    return gcd(y%x, x);

}
int tq(int n) {
    int ans = 1;
    while (n) {
        ans = ans * (n % 10);
        n = n / 10;
    }
    return ans;
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        a[i] = tq(i);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i] * a[j] <= 0) {
                continue;
            }
            if (gcd(a[i], a[j]) <= k) {
                ans++;
                ans %= 998244353;
            }
        }
    }
    std::cout << ans;
}

E. Pencils and Boxes

题目链接

Educational Codeforces Round 44 (Rated for Div. 2)--E. Pencils and Boxes

题解

中档题,题意大概是给定一串数字,问能否分成多个每部分不小于k的部分且每部分最大最小值之差不大于k。
因为连续大小的的数放置在一起可以保证最大最小值之差尽可能小,所以先将数排序。之后使用递推判断即可。满足两个条件的区间要么是一个连续的区间,要么不存在,如果这个区间内有任意一个位置作为结尾可行,则这个位置作为结尾可行。最后直接判断最后一个数字即可。注意要用二分来判断快速查询区间,不然有可能会被卡时间。
据说这题好像正解该是树状数组然而我并不会orz。

代码

#include <iostream>
#include <stdlib.h>
#include <algorithm>

using namespace std;
int a[500005];
int isyes[500005];
int n, d, k,cache;
int find(int maxt,int l,int r){
    if (a[(l+r)/2]<maxt&&a[(l+r)/2+1]>=maxt)return (l+r)/2;
    else if (a[(l+r)/2]>=maxt)return find(maxt,l,(l+r)/2-1);
    else if (a[(l+r)/2+1]<maxt)return find(maxt,(l+r)/2+1,r);
}
bool func(int a, int b) {
    return a < b;
}
int main() {
    cin >> n >> k >> d;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(&a[1],&a[n+1],func);
    for (int i = k; i <= n; i++) {
        if (a[i] - a[1] <= d)isyes[i] = isyes[i - 1] + 1;
        else {
            cache = i;
            break;
        }
    }
    /*for (int i = 1; i <= n; i++) {
        cout << isyes[i]<<' ';
    }
    cout<<endl;
    cout<<cache<<endl;*/
    if (cache==0)cache=n+1;
    for (int i = cache; i <= n; i++) {
        int pos=lower_bound(a+1,a+n+1,a[i]-d)-a-1;
        if (pos>i-k){
                isyes[i]=isyes[i-1];
                continue;
        }
        //cout<<pos<<' '<<a[i]<<' '<<d<<endl;
        if (isyes[i-k]-isyes[pos-1]>0)isyes[i]=isyes[i-1]+1;
        else isyes[i]=isyes[i-1];
        /*for (int j = i-k+1; a[i] - a[j] <= d; j--) {
            if (isyes[j - 1]) {
                isyes[i] = true;
                break;
            }
        }*/
    }
    isyes[n]-isyes[n-1]>0 ? cout << "YES" : cout << "NO";
}

C. Cut 'em all!

题目链接

Codeforces Round #484 (Div. 2)--C. Cut 'em all!

题解

中档题,题意大概是给定一个树,求最多可以删去多少条边满足剩下的每个联通分量均为偶数个节点。
emmm说实话我没想到什么特别的方法于是从叶子节点开始暴力……

代码

#include <bits/stdc++.h>
using namespace std;
int n,q,w;
map<int,int> a[100002];
bool boo[100002];
int link[100002][2];
map<int,map<int,int>> linknum;
int find(int from,int to){
    if (linknum[from][to]!=0)return linknum[from][to];
    if (a[to][0]==1)return 1;
    else {
        int num=1;
        for (int i=1;i<=a[to][0];i++){
            if (a[to][i]!=from)num+=find(to,a[to][i]);
        }
        linknum[from][to]=num;
        linknum[to][from]=num;
        return num;
    }
}
int main() {
    cin>>n;
    if (n%2==1){
        cout<<-1;
        return 0;
    }
    for (int i=1;i<=n-1;i++){
        cin>>q>>w;
        link[i][0]=q;
        link[i][1]=w;
        a[q][0]++;
        a[w][0]++;
        a[q][a[q][0]]=w;
        a[w][a[w][0]]=q;
    }
    int ans=0;
    int cache;
    for (int i=1;i<=n-1;i++){
        if (a[link[i][0]][0]==1||a[link[i][1]][0]==1)continue;
        else {
            if (find(link[i][0],link[i][1])%2==0)
            ans++;
            //cout<<link[i][0]<<' '<<link[i][1]<<endl;
        }
    }
    cout<<ans;
}

B. Bus of Characters

题目链接

Codeforces Round #484 (Div. 2)--B. Bus of Characters

题解

基础题,题意大概是给定一组不同宽度的座位,将两种人按照指定顺序插入。
直接模拟即可。

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <stdlib.h>
using namespace std;
struct seat{
    int loca;
    int num;
};
int n;
string s;
seat a[200005];
bool pd(seat a,seat b){
    return a.num<b.num;
}
int main() {
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i].num;
        a[i].loca=i;
    }
    cin>>s;
    sort(&a[1],&a[n+1],pd);
    int now =1;
    stack<int> st;
    for (int i=0;i<2*n;i++){
        if (s[i]=='0'){cout<<a[now].loca<<' ';st.push(a[now].loca);now++;}
        else {
            cout<<st.top()<<' ';
            st.pop();
        }
    }
}

A. Row

题目链接

Codeforces Round #484 (Div. 2)--A. Row

题解

基础题,题意大概是给定一串01数字组成的串,判断是否满足

  1. 没有两个1相邻
  2. 在满足第一条的情况下能否再将某个0改成1

模拟即可,注意首尾的判断以及长度为1时的判断

代码

#include <iostream>
#include <string>
#include <stack>
#include <stdlib.h>
using namespace std;
int n;
int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    bool yes=true;
    int num1=0,num11=0;
    int num0=0;
    for (int i=0;i<n;i++){
        if (s[i]=='1'){
            num0=0;
            num1++;
            num11++;
            if (num1==2)yes=false;
        }
        if (s[i]=='0'){
            num1=0;
            num0++;
            if (num0==3)yes=false;
        }
        if (num0==2&&i==1)yes=false;
        if (num0==2&&i==n-1)yes=false;
    }
    if (n==1&&s[0]=='0')cout<<"NO";
    else if (n==1&&s[0]=='1')cout<<"YES";
    else if (yes)cout<<"YES";
    else cout<<"NO";
    return 0;
}

D. XOR-pyramid

题目链接

Codeforces Round #483 (Div. 2)--D. XOR-pyramid

题解

中档题,题意大概是给出一个函数与多个询问,对每个询问求值。
由题中所给的公式可得f[a,b]=f[a,b-1] xor f[a+1,b]
直接进行动态规划即可

代码

#include <iostream>
#include <string>
#define MAAAX(a,b) (a>b?a:b)
using namespace std;
int n;
int a[5001][5001], m, l,r, c;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][i];
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n - i + 1; j++) {
            a[j][i + j - 1] = a[j][j + i - 2] ^ a[j + 1][j + i - 1];
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n - i + 1; j++) {
            a[j][i + j - 1] = MAAAX(a[j][i + j - 1],MAAAX(a[j][j + i - 2],a[j + 1][j + i - 1]));
        }
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l >> r;
        cout << a[l][r]<<endl;
    }
}

C. Finite or not?

题目链接

Codeforces Round #483 (Div. 2)--C. Finite or not?

题解

中档题。题意大概是求给定分数在某进制下是否为有限小数。
首先对给定分数进行化简,然后判断分母的所有因数是否是进制的因数,不是则为无限小数。
注意,codeforces上只要超过1e5的long long就会超时,所以要针对读入优化。

代码

#include <iostream>
#include <string>
using namespace std;
int n;
long long a, b, m, cache, c;
long long gcd(long long m, long long n)
{
    while (m>0)
    {
        c = n % m;
        n = m;
        m = c;
    }
    return n;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld %lld", &a, &b, &m);
        if (a == 0) {
            cout << "Finite" << endl;
            continue;
        }
        b  /= gcd(a, b);
        while ((cache = gcd(b, m)) != 1) {
            while (b%cache == 0)b /= cache;
        }
        cout << (b == 1 ? "Finite" : "Infinite") << endl;
    }
}

B. Minesweeper

题目链接

Codeforces Round #483 (Div. 2)--B. Minesweeper

题解

简单题。题意大概是给定一个扫雷地图,验证它的正确性。
直接模拟即可。

代码

#include <iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int c[10000];
int a, b;
char map[200][200];
int main() {
    cin >> a>>b;
    memset(map, '.', sizeof(map));
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            cin >> map[i][j];
            if (map[i][j] == '.')map[i][j] = '0';
        }
        cin.get();
    }
    int n;
    bool boo = true;
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            if (map[i][j] >= '0'&&map[i][j] <= '9') {
                n = 0;
                for (int k = i - 1; k <= i + 1; k++) {
                    for (int l = j - 1; l <= j + 1; l++) {
                        if (map[k][l] == '*')n++;
                    }
                }
                if (n != map[i][j] - '0')boo = false;
            }
        }
    }
    cout << (boo ? "YES" : "NO");
}