2017年西南民族大学程序设计竞赛-网络同步赛


A

做四个前缀和就行,一个#是1

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 1e3 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
char mp[qq][qq];
int dir[4][qq][qq];
 
int main() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", mp[i] + 1);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dir[0][i][j] += dir[0][i][j - 1];
            if (mp[i][j] == '#')    dir[0][i][j]++;
        }
        for (int j = m; j >= 1; --j) {
            dir[1][i][j] += dir[1][i][j + 1];
            if (mp[i][j] == '#')    dir[1][i][j]++;
        }
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            dir[2][j][i] += dir[2][j - 1][i];
            if (mp[j][i] == '#')    dir[2][j][i]++;
        }
        for (int j = n; j >= 1; --j) {
            dir[3][j][i] += dir[3][j + 1][i];
            if (mp[j][i] == '#')    dir[3][j][i]++;
        }
    }
    char opt[4];
    int x, y;
    while (q--) {
        scanf("%d%d%s", &x, &y, opt);
        int dr;
        if (opt[0] == 'L')  dr = 0;
        else if (opt[0] == 'R') dr = 1;
        else if (opt[0] == 'U') dr = 2;
        else    dr = 3;
        if (dir[dr][x][y] > 0)   puts("NO");
        else    puts("YES");
    }
    return 0;
}


B

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 1e6 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
char st[qq];
int main() {
    scanf("%s", st);
    int pre = st[0] - '0';
    int len = strlen(st);
    bool f = true;
    for (int i = 1; i < len; ++i) {
        if (pre != st[i] - '0') f = false;
    }
    if (f)  puts("YES");
    else    puts("NO");
    return 0;
}


C

直接对差值进行排序,然后依次取即可

注意差值相等的时候应该是早上甜蜜值越大的越靠前

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 1e6 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
struct Node {
    LL a, b;
    LL f;
    bool operator < (const Node &d) const {
        if (f == d.f)   return a > d.a;
        return f > d.f;
    }
}p[qq];
 
int main() {
    int n, k;   scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &p[i].a);
    }
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &p[i].b);
        p[i].f = p[i].a - p[i].b;
    }
    sort(p, p + n);
    LL ans = 0;
    for (int i = 0; i < k; ++i) {
        ans += p[i].a;
    }
    for (int i = k; i < n; ++i) {
        ans += p[i].b;
    }
    printf("%lld\n", ans);
    return 0;
}

D

做一下前缀和,然后判断区间和的正负性就行

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
LL sum[qq];
 
int main() {
    int n;  scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", sum + i);
        sum[i] += sum[i - 1];
    }
    int m;  scanf("%d", &m);
    LL ans = 0;
    for (int i = 1; i <= m; ++i) {
        int l, r;   scanf("%d%d", &l, &r);
        if (sum[r] - sum[l - 1] > 0) ans += sum[r] - sum[l - 1];
    }
    printf("%lld\n", ans);
    return 0;
}


E

考虑反面,用所有可能的情况减去不存在相邻两个是同色的情况

注意细节方面

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 5e3 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
LL quickPow(LL a, LL b) {
    if (a == 0) return 0;
    a %= MOD;
    LL ans = 1;
    while (b > 0) {
        if (b & 1)  ans = (ans * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return ans;
}
 
int main() {
    LL n, m;    scanf("%lld%lld", &n, &m);
    LL ans = quickPow(m, n), cns = (m % MOD) * (quickPow(m - 1, n - 1)) % MOD;
    printf("%lld\n", (ans - cns + MOD) % MOD);
    return 0;
}


F

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
char st[20][20];
int get(int x, int y) {
    if (x == 1 || y == 1 || x == 13 || y == 13) return 1;
    if (6 <= x && x <= 8 && 6 <= y && y <= 8)   return 4;
    if (4 <= x && x <= 10 && 4 <= y && y <= 10) return 3;
    return 2;
}
int main() {
    int n; 
    while (scanf("%d", &n) != EOF) {
        if (!n) break;
        for (int i = 1; i <= 13; ++i) {
            scanf("%s", st[i] + 1);
        }
        int ans = 0;
        for (int i = 1; i <= 13; ++i) {
            for (int j = 1; j <= 13; ++j) {
                if (st[i][j] == '#')    ans += get(i, j);
            }
        }
        printf("%.2lf\n", ans * 1.0 / n);
    }
    return 0;
}

G

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 1e6 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
string st[5] = {"Jin", "Mu", "Shui", "Huo", "Tu"};
int main() {
    int n;  cin >> n;
    int ali, bob;
    ali = bob = 0;
    while (n--) {
        string a, b;
        cin >> a >> b;
        int x, y;
        for (int i = 0; i < 5; ++i) {
            if (a == st[i]) x = i;
            if (b == st[i]) y = i;
        }
        if ((x == 0 && y == 1)) ali += 3;
        else if (y == 0 && x == 1)  bob += 3;
        else if (x == 1 && y == 4)  ali += 3;
        else if (y == 1 && x == 4)  bob += 3;
        else if (x == 4 && y == 2)  ali += 3;
        else if (y == 4 && x == 2)  bob += 3;
        else if (x == 2 && y == 3)  ali += 3;
        else if (y == 2 && x == 3)  bob += 3;
        else if (x == 3 && y == 0)  ali += 3;
        else if (y == 3 && x == 0)  bob += 3;
        else    ali += 1, bob += 1;
    }
    if (ali == bob) puts("Draw");
    else if (ali > bob)  puts("Alice");
    else    puts("Bob");
    return 0;
}

H

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
string a = "gu...", b = "The story is so boring. And I am so hungry!";
int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; ++i) {
            cout << a;
        }
        cout << endl;
        cout << b << endl;
    }
    return 0;
}

I

用二进制枚举所有情况

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
 
int main() {
    int n;  scanf("%d", &n);
    int ans = 0;
    for (int i = 0; i < (1 << n); ++i) {
        bool f = true;
        int cnt = 0;
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) cnt = 0;
            else    cnt++;
            if (cnt >= 2)    f = false;
        }
        if (f)  ans++;
    }
    printf("%d\n", ans);
    return 0;
}

J

pos[i] 代表元素i被交换到了什么位置

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
int f[205], pos[205];
char ini[qq];
 
int main() {
    scanf("%s", ini);
    int n;  scanf("%d", &n);
    char a[4], b[4];
    for (int i = 0; i < 26; ++i) f[i] = pos[i] = i;
    while (n--) {
        scanf("%s %s", a, b);
        int tmp = pos[b[0] - 'a'];
        pos[b[0] - 'a'] = pos[a[0] - 'a'];
        pos[a[0] - 'a'] = tmp;
    }
    int len = strlen(ini);
    for (int i = 0; i < len; ++i) {
        printf("%c", pos[ini[i] - 'a'] + 'a');
    }
    puts("");
    return 0;
}


K

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
 
using namespace std;
 
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
 
const int qq = 5e3 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
int vis[qq];
 
int main() {
    int n, m;   scanf("%d%d", &n, &m);
    int maxn = 0;
    for (int l, r, i = 0; i < n; ++i) {
        scanf("%d%d", &l, &r);
        for (int j = l; j <= r; ++j) {
            vis[j]++;
            maxn = max(maxn, vis[j]);
        }
    }
    int ans = (int)ceil(maxn * 1.0 / m);
    printf("%d\n", ans);
    return 0;
}
相关文章
相关标签/搜索