ACM-ICPC 2017 南宁赛区现场赛 A ,F,H,J,L

Abiyoyo

/*
 * [链接]:https://nanti.jisuanke.com/t/A1530
 *
 * [题意]:复读机
 *
 * [分析]:
 *
 * [tricks]:
 *
 * [时间复杂度]
 *
 *
 *
 *
 *
 * */

#include <bits/stdc++.h>

#define  ll long long

using namespace std;

void scan() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scan();
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        while(n--) printf("Abiyoyo, Abiyoyo.\n");
        printf("Abiyoyo, yo yoyo yo yoyo.\n");
        printf("Abiyoyo, yo yoyo yo yoyo.\n");
    }
    return 0;
}

 The Chosen One

 

/*
 * [链接]:https://nanti.jisuanke.com/t/A1535
 *
 * [题意]:给你一个n,每个位置上的数字分别为1,2,3,...,n。重复删除奇数位的数字直到剩余一个数字。
 * 问:最后一个数字是多少。
 *
 * [分析]:  暴力打表发现是这样的1,2,2,4,4,4,4,8,8,8,8,8,8,8,8.....
 * 大数模拟一下*2的前缀和和当前的答案
 *
 * [tricks]:
 *
 * [时间复杂度]:t*log2(10^50)*50
 *
 *
 *
 *
 *
 * */

#include <bits/stdc++.h>

#define  ll long long

using namespace std;

void scan() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}


string add(string a, string b) {
    string c;
    int len1 = a.length();
    int len2 = b.length();
    int len = max(len1, len2);
    for (int i = len1; i < len; i++)
        a = "0" + a;
    for (int i = len2; i < len; i++)
        b = "0" + b;
    int ok = 0;
    for (int i = len - 1; i >= 0; i--) {
        char temp = a[i] + b[i] - '0' + ok;
        if (temp > '9') {
            ok = 1;
            temp -= 10;
        } else ok = 0;
        c = temp + c;
    }
    if (ok) c = "1" + c;
    return c;
}


string mul(string a, int b) {
    string c;
    char s;
    int len = a.length();
    int ok = 0;
    for (int i = len - 1; i >= 0; i--) {
        int temp = (a[i] - '0') * b + ok;
        ok = temp / 10;
        s = temp % 10 + '0';
        c = s + c;
    }
    while (ok) {
        s = ok % 10 + '0';
        c = s + c;
        ok /= 10;
    }
    return c;
}

bool judge(string a, string b) {
    if (a.size() == b.size()) {
        int sz = a.size();
        for (int i = 0; i < sz; i++) {
            if (a[i] == b[i]) ;
            else return a[i]>b[i];
        }
        return 1;
    }
    return a.size() > b.size();
}


string sub(string a, string b) {
    string c;
    bool ok = 0;
    int len1 = a.length();
    int len2 = b.length();
    int len = max(len1, len2);
    for (int i = len1; i < len; i++)
        a = "0" + a;
    for (int i = len2; i < len; i++)
        b = "0" + b;
    if (a < b) {
        string temp = a;
        a = b;
        b = temp;
        ok = 1;
    }
    for (int i = len - 1; i >= 0; i--) {
        if (a[i] < b[i]) {
            a[i - 1] -= 1;
            a[i] += 10;
        }
        char temp = a[i] - b[i] + '0';
        c = temp + c;
    }
    int pos = 0;
    while (c[pos] == '0' && pos < len) pos++;
    if (pos == len) return "0";
    if (ok) return "-" + c.substr(pos);
    return c.substr(pos);
}

string ss[1000], ans[1000];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scan();

    ss[1] = "1";ans[0]="0";
    ans[1] = "1";ss[0]="0";
    string now = "1";
    for (int i = 2; i <= 200; i++) {
        now = mul(now, 2);
        ans[i] = now;
        ss[i] = add(now, ss[i - 1]);
    }
    int t;
    cin >> t;
    while (t--) {
        string zx;
        cin >> zx;
        int pos = 1;
        for (int i = 1; i <= 200; i++) {
            if (judge(zx, ss[i])) pos = i;
            else {
                pos=i;
                zx=sub(zx,ss[i-1]);
                if(zx=="0") pos--;
                break;
            }
        }
        cout<<ans[pos]<<endl;
    }
    return 0;
}

The Game of Life

/*
 * [链接]:https://nanti.jisuanke.com/t/A1537
 *
 * [题意]:给出n*m的字符型矩阵,'.'表示不存在细胞,’#‘表示存在。
 * 细胞能够分裂的几种情况是:
 * 若当前活着的细胞旁边(8联通)存在的活着的细胞数小于2,则当前细胞死亡;
 * 若当前活着的细胞旁边存在的活着的细胞数等于2,则当前细胞能够进行到下一次的分裂;
 * 若当前活着的细胞旁边存在的活着的细胞数等于3,则当前位置新生成一个细胞;
 * 若当前的细胞旁边存在的活着的细胞数大于3,则当前细胞死亡;
 *
 * 问:在分裂321次过程中,第几次细胞的数目达到最大,数目最大是多少,和第321次细胞的数量.
 *
 * [分析]:暴力模拟即可
 * [tricks]:注意边界的取值。
 *
 * [时间复杂度]:t*321*
 *脑子不清醒,调的快心肌梗塞了。
 * */


#include <bits/stdc++.h>

#define  ll long long
using namespace std;

void scan() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

const int maxn = 1e3 + 7;
bool vis[maxn][maxn];
string ss[maxn];

int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
int dy[] = {-1, 0, 1, -1, 0, 1, 1, -1};

struct node {
    int x, y;

    node() {}

    node(int _x, int _y) {
        x = _x, y = _y;
    }

    bool operator!=(const node &a) const {
        return !(a.x == x && a.y == y);
    }

    bool operator==(const node &a) const {
        return (a.x == x && a.y == y);
    }

    bool operator<(const node &a) const {
        return x == a.x ? y < a.y : x < a.x;
    }
} a[maxn * maxn + 1], now[maxn * maxn + 1];

const int zx = 400;


int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scan();
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) cin >> ss[i];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (ss[i][j] == '#') {
                    a[cnt++] = node(i + zx, j + zx);
                    vis[i + zx][j + zx] = 1;
                }
            }
        }
        int turnnum = 0, maxnum = cnt;
        for (int turn = 1; turn <= 321; turn++) {
            int ret = 0;
            for (int i = 0; i < cnt; i++) {
                for (int j = 0; j < 8; j++) {
                    now[ret++] = node(dx[j] + a[i].x, dy[j] + a[i].y);
                }
            }
            sort(now, now + ret);
            for (int i = 0; i < cnt; i++) {
                if (*lower_bound(now, now + ret, a[i]) != a[i]) vis[a[i].x][a[i].y] = 0;
            }
            int tmp = 0;
            cnt = 0;
            while (tmp < ret) {
                int step = 0;
                while (tmp + step < ret && now[tmp] == now[tmp + step]) step++;
                if (step < 2) {
                    vis[now[tmp].x][now[tmp].y] = 0;
                } else if (step == 2) {
                    if (vis[now[tmp].x][now[tmp].y] == 1) a[cnt++] = now[tmp];
                } else if (step == 3) {
                    vis[now[tmp].x ][now[tmp].y] = 1, a[cnt++] = now[tmp];
                } else {
                    vis[now[tmp].x][now[tmp].y] = 0;
                }
                tmp += step;
            }
            if (cnt > maxnum) turnnum = turn, maxnum = cnt;
            if (cnt == 0) break;
        }
        cout << turnnum << " " << maxnum << " " << cnt << endl;
    }
    return 0;
}

 Rearrangement

/*
 * Rearrangement
 *
 * [链接]:https://nanti.jisuanke.com/t/A1539
 *
 * [题意]:给出2*n个数,问排成两行,问是否可以使得相邻的数的和是否能够整除3;
 *
 * [分析]:一般的写法就是考虑大范围内不存在的情况,再细细的进行分类讨论。
 * a[i]:表示i数字出现的次数;
 * 首先考虑0和0是不能放在一起的,因此a[0]>n肯定是不行的。
 * 再考虑存在一个0,如果同时存在1和2,这样必然存在1和2相邻;
 * 最后考虑存在两个0,很显然要错开两个0,显然中间要存在奇数个a[1]或a[2];
 * [tricks]:
 * 无。
 * [时间复杂度]:t*2*n
 * */


#include <bits/stdc++.h>

#define  ll long long
using namespace std;

void scan() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}


int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scan();
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[4], x;
        for (int i = 0; i <= 2; i++) a[i] = 0;
        for (int i = 0; i < 2 * n; i++) cin >> x, a[x % 3]++;

        if (a[0] > n) cout << "NO" << endl;
        else {
            if (a[0] == n) cout << "YES" << endl;
            else if (a[0] == 0) {
                if (a[1] && a[2]) cout << "NO" << endl;
                else cout << "YES" << endl;
            } else if (a[0] == 1) {
                if (a[1] >= 1 && a[2] >= 1) cout << "NO" << endl;
                else cout << "YES" << endl;
            } else if (a[1] == 0 || a[2] == 0) cout << "YES" << endl;
            else if (a[0] == 2) {
                if (a[1] % 2 == 0 && a[2] % 2 == 0) cout << "NO" << endl;
                else cout << "YES" << endl;
            } else cout << "YES" << endl;
        }


    }
    return 0;
}

 

Twice Equation 

/*
 * [链接]:https://nanti.jisuanke.com/t/A1541
 *
 * [题意]:找到最小的n且大于L的数字满足2*m(m+1)=n*(n+1);
 *
 * [分析]:暴力打表;ans[i]=ans[i-1]*6-ans[i-2]+2;
 *
 *
 *
 *
 * [tricks]:
 *
 * 真没意思,一套题居然出两个大数
 *
 * [时间复杂度]:
 *
 *
 *
 *
 *
 * */

#include <bits/stdc++.h>

#define  ll long long

using namespace std;

void scan() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}


string add(string a, string b) {
    string c;
    int len1 = a.length();
    int len2 = b.length();
    int len = max(len1, len2);
    for (int i = len1; i < len; i++)
        a = "0" + a;
    for (int i = len2; i < len; i++)
        b = "0" + b;
    int ok = 0;
    for (int i = len - 1; i >= 0; i--) {
        char temp = a[i] + b[i] - '0' + ok;
        if (temp > '9') {
            ok = 1;
            temp -= 10;
        } else ok = 0;
        c = temp + c;
    }
    if (ok) c = "1" + c;
    return c;
}


string mul(string a, int b) {
    string c;
    char s;
    int len = a.length();
    int ok = 0;
    for (int i = len - 1; i >= 0; i--) {
        int temp = (a[i] - '0') * b + ok;
        ok = temp / 10;
        s = temp % 10 + '0';
        c = s + c;
    }
    while (ok) {
        s = ok % 10 + '0';
        c = s + c;
        ok /= 10;
    }
    return c;
}

bool judge(string a, string b) {
    if (a.size() == b.size()) {
        int sz = a.size();
        for (int i = 0; i < sz; i++) {
            if (a[i] == b[i]) ;
            else return a[i]>b[i];
        }
        return 1;
    }
    return a.size() > b.size();
}


string sub(string a, string b) {
    string c;
    bool ok = 0;
    int len1 = a.length();
    int len2 = b.length();
    int len = max(len1, len2);
    for (int i = len1; i < len; i++)
        a = "0" + a;
    for (int i = len2; i < len; i++)
        b = "0" + b;
    if (a < b) {
        string temp = a;
        a = b;
        b = temp;
        ok = 1;
    }
    for (int i = len - 1; i >= 0; i--) {
        if (a[i] < b[i]) {
            a[i - 1] -= 1;
            a[i] += 10;
        }
        char temp = a[i] - b[i] + '0';
        c = temp + c;
    }
    int pos = 0;
    while (c[pos] == '0' && pos < len) pos++;
    if (pos == len) return "0";
    if (ok) return "-" + c.substr(pos);
    return c.substr(pos);
}

string ss[1000], ans[1000];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scan();

    ans[0]="0";
    ans[1] = "3";
    string now = "1";
    for (int i = 2; i <= 500; i++) ans[i]=add(sub(mul(ans[i-1],6),ans[i-2]),"2");
    int t;
    cin >> t;
    while (t--) {
        string zx;
        cin >> zx;
        for(int i=0;i<=500;i++){
            if(judge(ans[i],zx)) {
                cout<<ans[i]<<endl;
                break;
            }
        }
    }
    return 0;
}

 

 

上一篇:Dynamics 365 如何关闭Lookup字段的最近使用记录


下一篇:用Latex高效整理你的ACM-ICPC模板