“强智杯“2020年湖南省大学生计算机程序设计竞赛——ABDGHI

oj: 链接A.2020oj: 链接题解直接暴力维护即可。代码#include <bits/stdc++.h>#define PI atan(1.0)*4#define rp(i,s,t) for ( int i = (s); i <= (t); i++)#define RP(i,t,s) for ( int i = (t); i >= (s); i--)#define s

mumei314

1451人浏览 · 2021-03-12 20:00:29

mumei314 · 2021-03-12 20:00:29 发布

oj: 链接

A.2020

oj: 链接

题解

直接暴力维护即可。

代码

#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for ( int i = (s); i <= (t); i++)
#define RP(i,t,s) for ( int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
void solve(){
    int n;
    while(cin>>n){
        string s;cin>>s;
        int ans=0;
        rp(i,0,n-1){
            if(i+3<=n-1&&s[i]=='2'&&s[i+1]=='0'&&s[i+2]=='2'&&s[i+3]=='0'){
                i=i+3;
                ans++;
            }
            // outval2(i,ans);
        }
        cout<<ans<<endl;
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    //debug = 1;
#endif
    //time_t beg, end;
    //if(debug) beg = clock();
    solve();
    /*
    if(debug) {
        end = clock();
        printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    }
    */
    return 0;
}

B.2020 vs 2018

oj: 链接

题解

观察在 $2018$ 和 $2020$ 的图像可以发现，
最明显的区别在于 $2018$ 多了一个 $1$ 。
因此我们直接暴力枚举是否有 $1$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a) for(int i = 0, len = a; i < len; ++i)
#define _rep(i, a, b) for(int i = a, len = b; i <= len; ++i)
#define outval(a) cout << "debuging|" << #a << ":" << a << "\n";
#define dg if(debug)
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
int debug = 0;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while(ch < '0' || ch > '9') {
        f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

struct poi {

};

int n, m;
char s[57][57];
void init() {
    _rep(i,1,n) scanf("%s",s[i]+1);
    _rep(i,1,n){
        dg outval(i);
        _rep(j,i,n){
            dg outval(j);
            _rep(k,1,m){
                int f=1;
                if(i>1&&s[i-1][k]=='o') continue;
                if(j<n&&s[j+1][k]=='o') continue;
                _rep(l,i,j){
                    if(s[l][k]!='o'){
                        f=0;
                        break;
                    }
                    if(k>1){
                        if(s[l][k-1]=='o'){
                            f=0;
                            break;
                        }
                    }
                    if(k<m){
                        if(s[l][k+1]=='o'){
                            f=0;
                            break;
                        }
                    }
                }
                if(f){
                    puts("2018");
                    return ;
                }
            }
        }
    }
    

    _rep(i,1,m){
        _rep(j,i,m){
            _rep(k,1,n){
                int f=1;
                if(i>1&&s[k][i-1]=='o') continue;
                if(j<m&&s[k][j+1]=='o') continue;
                _rep(l,i,j){
                    if(s[k][l]!='o'){
                        f=0;
                        break;
                    }
                    if(k>1){
                        if(s[k-1][l]=='o'){
                            f=0;
                            break;
                        }
                    }
                    if(k<n){
                        if(s[k+1][l]=='o'){
                            f=0;
                            break;
                        }
                    }
                }
                if(f){
                    puts("2018");
                    return ;
                }
            }
        }
    }
    puts("2020");
}


int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    // debug = 1;
#endif
    while(~scanf("%d%d",&n,&m)) init();
    return 0;
}

D.String Commutativity

oj: 链接

题解

如果两个串有相同的最短循环节，则这两个串符合题目要求。用kmp求最短循环节，但kmp求出的最短循环节不一定符合题意，例如aba的最短循环节为ab，而kmp求出的为aba，所以应排除这种情况。即用m%x!=0判断是否最后一个循环节是否完全循环

代码

#include <cstring>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
const int maxn=1e6+7;
const int INF=0x3f3f3f3f;
#define M 50015
int next1[maxn];
char str[maxn],mo[maxn];
int ans;
map<string,int> mp;
string tran(int x){
    string a;
    for(int i=0;i<x;i++){
        a.push_back(mo[i]);
    }
    return a;
}
void getnext()
{
    int i=0,j=-1,m=strlen(mo);
    while(i<m){
        if(j==-1||mo[i]==mo[j])
            next1[++i]=++j;
        else
            j=next1[j];
    }
}
int main()
{

    int t;
    while(~scanf("%d",&t)){
        mp.clear();
        long long sum=0;
        while(t--){
            ans=0;
            scanf("%s",mo);
            next1[0]=-1;
            getnext();
            int m=strlen(mo);
            int x=m-next1[m];
            if(x<m&&m%x!=0){
                x=m;
            }
            
            //printf("x:%d\n", x);
            string y=tran(x);
            mp[y]++;

        }
        map<string,int>::iterator it;
        it=mp.begin();
        while(it!=mp.end()){
            int n=it->second;
            sum+=1LL*n*(n-1)/2;
            it++;
        }
        printf("%lld\n",sum);
    }
    return 0;
}

G.奇矩阵

oj: 链接

题解

可以直接暴力枚举过，时间复杂度: $O(n^{2})$ 。
$O (n)$ 的做法：
先说结论
记录每一行数的和的奇偶性，
如果奇数的次数是否大于 $1$ 且偶数的次数大于 $1$ 肯定不是奇矩阵，否则是。
证明如下：
假设当前有 $m$ 列数，取两行数分别为：
$x_{1},x_{2},...,x_{m}$ 。
$y_{1},y_{2},...,y_{m}$ 。
令 $d_{1}=x_{1}-y_{1}$ ，
$d_{2}=x_{2}-y_{2}$ ，
$d_{3}=x_{3}-y_{3}$ ，
…
$d_{m}=x_{m}-y_{m}$
假设两行数的和都为偶数，那么可以得到
$d_{1}+d_{2}+...+d_{m})$ % $2 = 0$ 。
因为题目给的是绝对值求和，
如果当前差值是 $d_{i}$ ，
如果 $d_{i}$ 为正数没有影响，
如果 $d_{i}$ 为负数的话对答案的影响是加上 $2\times |d_{i}|$ 。
那么可以发现 $(d_{1}+d_{2}+...+d_{m}+2\times |d_{i}|)$ % $2 = 0$ ，即对答案的奇偶性没有影响。
因此结论得证。

代码

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a) for(int i = 0, len = a; i < len; ++i)
#define _rep(i, a, b) for(int i = a, len = b; i <= len; ++i)
#define outval(a) cout << "debuging|" << #a << ":" << a << "\n";
#define dg if(debug)
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
int debug = 0;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while(ch < '0' || ch > '9') {
        f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

struct poi {

};

int n, m;
int num[2];

void init() {
    num[0] = num[1] = 0;
}

int sol() {
    init();
    _for(i, n) {
        LL sum = 0;
        _for(j, m) sum += read();
        ++num[sum & 1];
    }
    if(num[0] > 1 || num[1] > 1) return 0;
    return 1;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    debug = 1;
#endif
    while(cin>>n>>m) {
        printf("%s\n", sol() ? "Yes":"No");
    }
    return 0;
}

H.矩阵并

oj: 链接

题解

分情况容斥一下即可求出答案。
参考下图
在这里插入图片描述

代码

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a) for(int i = 0, len = a; i < len; ++i)
#define _rep(i, a, b) for(int i = a, len = b; i <= len; ++i)
#define outval(a) cout << "debuging|" << #a << ":" << a << "\n";
#define dg if(debug)
typedef long long LL;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1005;
const LL mod = 1000000007;
int debug = 0;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

struct poi {
    
};

LL a, b;

void exgcd(LL a, LL b, LL &g, LL &x, LL &y) {
    if (!b) {
        g = a;
        x = 1;
        y = 0;
    } else {
        exgcd(b, a % b, g, y, x);
        y -= x * (a / b);
    }
}
LL inv(LL x, LL mod) {
    LL a, k, g;
    exgcd(x, mod, g, a, k);
    if(a < 0) a += mod;
    return a;
}

LL getval(LL a, LL b) {
    LL ans = 0;
    ans += a * a % mod * b % mod * b;
    ans += a * b % mod * b % mod;
    ans += a * a % mod * b % mod;
    ans += a * b % mod;
    ans %= mod;
    ans *= inv(4, mod);
    return ans % mod;
}

int sol() {
    LL x = read(), xx = read(), y = read(), yy = read();
    LL ans = 0;
    ans += getval(a, b);
    dg printf("累积：%lld\n", getval(a, b));

    LL w1 = max(0LL, min(b, yy) - y);
    LL box1 = w1 * (w1 + 1) % mod * inv(2, mod) % mod * max(0LL, a - xx) % mod * (xx - x) % mod;
    LL w2 = max(0LL, min(a, xx) - x);
    if(a < x) w2 = 0;
    dg printf("w1:%lld\tw2:%lld\n", w1, w2);
    LL box2 = w2 * (w2 + 1) % mod * inv(2, mod) % mod * max(0LL, b - yy) % mod * (yy - y) % mod;
    LL box3 = max(0LL, a - xx) * max(0LL, b - yy) % mod * (xx - x) % mod * (yy - y) % mod;
    LL ans2 = box1 + box2 + box3 + getval(max(0LL, min(a, xx) - x), max(0LL, min(b, yy) - y)); ans2 %= mod;
    dg printf("box1:%lld\tbox2:%lld\tbox3:%lld\n", box1, box2, box3);
    dg printf("减去：%lld\n", ans2);

    ans += mod - ans2;
    LL ans3 = (xx - x) * (yy - y) % mod * a % mod * b % mod;
    ans += ans3;
    dg printf("额外：%lld\n", ans3);

    ans %= mod;
    printf("%lld\n", ans);
    return 0;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    // debug = 1;
#endif
    while(~scanf("%lld%lld", &a, &b)) {
        sol();
    }
    return 0;
}

I.共线点

oj: 链接

题解

首先把三个线段按照高度排序，
然后用最高的线段的左端点和最低的线段的左端点连接成一条直线，
求出这个直线方程，把中间线段的 $y$ 值带入，这样求出的是有效区间的左端点。
同理可以得到有效区间的右端点。
判断一下中间线段是否和这个有效区间是否有交点即可。
求端点可以利用两点式快速求出来。

代码

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a) for(int i = 0, len = a; i < len; ++i)
#define _rep(i, a, b) for(int i = a, len = b; i <= len; ++i)
#define outval(a) cout << "debuging|" << #a << ":" << a << "\n";
#define dg if(debug)
typedef long long LL;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1005;
int debug = 0;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while(ch < '0' || ch > '9') {
        f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

struct poi {
    int a, b, y;
    bool operator<(const poi &b) const {
        if(y != b.y) return y < b.y;
        else if(a != b.a) return a < b.a;
        else return this->b < b.b;
    }
};

poi a[3];

void init() {

}

int sol() {
    _rep(i, 1, 2) {
        int aa, bb, yy;
        scanf("%d%d%d", &aa, &bb, &yy);
        a[i] = {aa, bb, yy};
    }
    sort(a, a + 3);
    double x1 = 1.0 * (a[2].a - a[0].a) / (a[2].y - a[0].y) * (a[1].y - a[0].y) + a[0].a;
    double x2 = 1.0 * (a[2].b - a[0].b) / (a[2].y - a[0].y) * (a[1].y - a[0].y) + a[0].b;
    dg printf("xx1:%.2f\txx2:%.2f\n", x1, x2);
    if(x1 - eps <= a[1].b && x2 + eps >= a[1].a) return 1;
    return 0;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    debug = 1;
#endif
    int aa, bb, yy;
    while(~scanf("%d%d%d", &aa, &bb, &yy)) {
        a[0] = {aa, bb, yy};
        printf("%s\n", sol () ?"Yes":"No");
    }
    return 0;
}