Visors's blog

2021 SCUEC Rookie Cup Editorial
By Visors, history, 4 years ago, In English

比赛传送门： [contest:319429]

Idea:aabbccSu

Tutorial is loading...
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;
#define ENDL "\n"
#define lowbit(x) (x & (-x))
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 2e5 + 10;

bool isLeap(int x) {
    if ((x % 4 == 0 && x % 100) || x % 400 == 0) return 1;
    return 0;
}


int p[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int q[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int v[] = {0, 1, 2, 4, 8, 16, 32};

//2021/1/1 Friday
int getWeek(int Y, int M, int D) {
    int y = 2021, m = 1, d = 1, w = 5;
    while (y != Y || m != M || d != D) {
        if (!isLeap(y)) {
            if (d + 1 > p[m]) {
                if (m + 1 > 12) y++, m = 1, d = 1;
                else {
                    m++;
                    d = 1;
                }
            } else d++;
        } else {
            if (d + 1 > q[m]) {
                if (m + 1 > 12) y++, m = 1, d = 1;
                else {
                    m++;
                    d = 1;
                }
            } else d++;
        }

        w = w + 1 > 7 ? 1 : w + 1;
    }
    return w;
}

int solve(int y, int m, int d, int w, int Y, int M, int D) {
    int ans = 0;
    while (y != Y || m != M || d != D) {
        if (!isLeap(y)) {
            if (d + 1 > p[m]) {
                if (m + 1 > 12) y++, m = 1, d = 1;
                else {
                    m++;
                    d = 1;
                }
            } else d++;
        } else {
            if (d + 1 > q[m]) {
                if (m + 1 > 12) y++, m = 1, d = 1;
                else {
                    m++;
                    d = 1;
                }
            } else d++;
        }
        if (w < 7) ans += v[w];
        else ans /= 2;
        w = w + 1 > 7 ? 1 : w + 1;
    }
    if (w < 7) ans += v[w];
    else ans /= 2;
    return ans;
}

//首先计算出起始天是周几，然后向后模拟
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    int y1, m1, d1, y2, m2, d2;
    cin >> T;
    while (T--) {
        cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;
        int now = getWeek(y1, m1, d1);
        cout << solve(y1, m1, d1, now, y2, m2, d2) << ENDL;
    }
    return 0;
}

Idea:SHIYAOHUA

Tutorial is loading...
#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"

char s[20];

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        double sum = 0.0;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%s", s);
            if (isalpha(s[0])) continue;
            else {
                sum += atof(s), cnt++;
            }
        }
        if (cnt == 0) puts("0");
        else printf("%.10lf\n", sum / cnt);
    }
    return 0;
}

Idea:waswasqq

Tutorial is loading...
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    //scanf("%d",&t);
    cin >> t;
    while (t--) {
        int n;;
        //scanf("%d",&n);
        cin >> n;
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            int x;
            //scanf("%d",&x);
            cin >> x;
            sum += x;
            sum %= mod;
        }
        n--;
        while (n--)//也可以手写快速幂
        {
            sum *= 2;
            sum %= mod;
        }
        //printf("%d\n",sum);
        cout << sum << '\n';
    }
}

Idea:hushnow

Tutorial is loading...
#include<bits/stdc++.h>

using namespace std;
#define ll long long
int n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};//方向数组
bool tu[5][5];//表示是否走过
int sum = 0;

void dfs(int x, int y, int num)//x，y是当前到的格子，num是当前已经排了的蛇的长度
{
    if (num == m)//当排到蛇的长度为m时即可认为是一种情况，并sum++
    {
        sum++;
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < n && (!tu[x + dx[i]][y + dy[i]])) {
            tu[x + dx[i]][y + dy[i]] = true;//走过的用true表示已经走过
            dfs(x + dx[i], y + dy[i], num + 1);
            tu[x + dx[i]][y + dy[i]] = false;//递归回来后将其再次标记为未走过
        }
    }
}

int main() {
    cin >> n >> m;
    memset(tu, false, sizeof(tu));//将图表示为都没有走过
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            tu[i][j] = true;//走过的用true表示已经走过
            dfs(i, j, 1);
            tu[i][j] = false;//递归回来后将其再次标记为未走过
        }
    }
    cout << sum << endl;
}

Idea:tczzz

Tutorial is loading...

Written by:tczzz

#include <bits/stdc++.h>

using namespace std;
#define ll long long
int tree[110000][20];
int n, m;
struct node {
    int i;
    int j;
};
queue<node> q;
bool f = 0;

void bfs() {
    while (!q.empty()) {
        node s = q.front();
        q.pop();
        if (!f) {
            cout << tree[s.i][s.j];
            f = 1;
        } else {
            cout << ' ' << tree[s.i][s.j];
        }
        if (s.j * 2 <= (1 << m) - 1) {
            node nw;
            nw.i = s.i;
            nw.j = s.j * 2;
            q.push(nw);
        }
        if (s.j * 2 + 1 <= (1 << m) - 1) {
            node nw;
            nw.i = s.i;
            nw.j = s.j * 2 + 1;
            q.push(nw);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    int w;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= (1 << m) - 1; j++) {
            cin >> tree[i][j];
        }
    }
    for (int i = 1; i <= n; i <<= 1) {
        for (int j = i; j < i << 1 && j <= n; j++) {//把每层“节点”的第一个节点扔到队列
            node s;
            s.i = j;
            s.j = 1;
            q.push(s);
        }
        bfs();//一层的节点扔完后进行bfs
    }
    cout << endl;
    return 0;
}

Written by:Visors

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<int> > v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    v.resize(n, vector<int>(pow(2, m) - 1));
    for (auto &i : v)
        for (int &j : i)
            cin >> j;
    int depth = log2(n);
    bool first = true;
    for (int i = 0; i < depth; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = pow(2, i); k < min((int) pow(2, i + 1), n + 1); k++) {
                for (int t = pow(2, j); t < pow(2, j + 1); t++) {
                    if (first) {
                        cout << v[k - 1][t - 1];
                        first = false;
                    } else cout << ' ' << v[k - 1][t - 1];
                }
            }
        }
    }
    cout << endl;
    return 0;
}

Idea:rainbu5

Tutorial is loading...
#include<bits/stdc++.h>  

using namespace std;  
typedef long long ll;  
const int N = 100000 + 5 ;  
char str[N];  
int main()  
{  
    //freopen("in.txt","r",stdin);  
	  scanf("%s",str);  
	 int len = strlen(str);  
	 int res = 0 ;  
	 stack <int> st;  
	 for(int i = 0 ;i < len ; i ++) {  
        char c = str[i] ;  
		if(st.size() && c == ']' && str[st.top()]=='[')st.pop();  
	    else if(st.size() && c == '}' && str[st.top()]=='{')st.pop();  
	    else if(st.size() && c == ')' && str[st.top()]=='(')st.pop();  
		else st.push(i);  
  
		if(st.size())res = max(res,i - st.top()); 
	    else res = max(res , i + 1);  
	 }  
     printf("%d",res);  
	 return 0;  
}

Idea:Lian

Tutorial is loading...
#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
const int maxn = 2050;
const int Mod = 1e9 + 7;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

int n, m;
int a[maxn][maxn];
ll d[maxn][maxn];
bool vis[maxn][maxn];

bool check(int r, int c) {
    if (r <= 0 || c <= 0 || r > n || c > m) return 0;
    return 1;
}

void dfs(int x, int y) {
    vis[x][y] = 1;
    for (int i = 0, r, c; i < 4; i++) {
        r = x + dx[i], c = y + dy[i];
        if (!check(r, c)) continue;
        if (!vis[r][c] && a[r][c] > a[x][y]) dfs(r, c);
        if (a[r][c] > a[x][y]) d[x][y] = (d[x][y] + d[r][c]) % Mod;
    }
}

int main() {
    //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
                vis[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int cnt = 0;
                for (int k = 0, r, c; k < 4; k++) {
                    r = i + dx[k], c = j + dy[k];
                    if (check(r, c) && a[r][c] > a[i][j]) cnt++;
                }
                d[i][j] = (cnt == 0 ? 1 : 0);  //d数组的初始化
            }
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (!vis[i][j]) dfs(i, j);  //每个点只访问一次，那么访问过的点就无需再搜
                ans = (ans + d[i][j]) % Mod;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Idea:lancee

Tutorial is loading...
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>

using namespace std;

int n, m, sum, ans;
char maze[1005][1005];
bool vis[1005][1005];
int odddis[6][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}, {-1,-1}, {1,-1}};
int evendis[6][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}, {-1,1}, {1,1}};


struct point {
    int x;
    int y;
};

int gcd(int a, int b) {
    return b > 0 ? gcd(b, a % b) : a;
}

bool judge;

void bfs(int x, int y) {
    queue<point> que;
    int cnt = 0;
    if (!vis[x][y]) {
        point pos;
        pos.x = x;
        pos.y = y;
        if (maze[x][y] == '*') {
            judge = true;
        }
        vis[x][y] = true;
        cnt++;
        que.push(pos);
        while (!que.empty()) {
            if (que.front().x % 2 == 0) {
                for (int i = 0; i < 6; i++) {
                    int xx = que.front().x + odddis[i][0];
                    int yy = que.front().y + odddis[i][1];
                    if (xx >= 0 && yy >= 0 && xx < n && yy < m
                        && maze[xx][yy] != '#' && !vis[xx][yy]) {
                        point temp;
                        temp.x = xx;
                        temp.y = yy;
                        que.push(temp);
                        vis[xx][yy] = true;
                        cnt++;
                        if (maze[xx][yy] == '*')
                            judge = true;
                    }
                }
            } else if (que.front().x % 2 == 1) {
                for (int i = 0; i < 6; i++) {
                    int xx = que.front().x + evendis[i][0];
                    int yy = que.front().y + evendis[i][1];
                    if (xx >= 0 && yy >= 0 && xx < n && yy < m
                        && maze[xx][yy] != '#' && !vis[xx][yy]) {
                        point temp;
                        temp.x = xx;
                        temp.y = yy;
                        que.push(temp);
                        vis[xx][yy] = true;
                        cnt++;
                        if (maze[xx][yy] == '*')
                            judge = true;
                    }
                }
            }
            que.pop();
        }
    }
    //cout << cnt << endl;
    if (judge == true)sum += cnt;
}

int main() {
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        ans = 0;
        sum = 0;
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> maze[i][j];
                if (maze[i][j] == '.' || maze[i][j] == '*')
                    ans++;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maze[i][j] != '#' && !vis[i][j]) {
                    judge = false;
                    bfs(i, j);
                }
            }
        }
        int num = gcd(ans, sum);
        if (sum == 0)
            cout << 0 << endl;
        else if (sum == num)
            cout << 1 << endl;
        else
            cout << sum / num << "/" << ans / num << endl;
        memset(vis, 0, sizeof(vis));
    }
}

Idea:Visors

粗暴复刻了 1345C - Hilbert's Hotel

Tutorial is loading...
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> v(n);
        vector<bool> book(n);
        for (int &it:v) cin >> it;
        for (int i = 0, tmp; i < n; i++) {
            tmp = (((v[i] + i) % n) + n) % n; //避免%出负数
            if (!book[tmp]) book[tmp] = true;
            else {
                cout << "YES" << endl;
                goto over;
            }
        }
        cout << "NO" << endl;
        over:;
    }
    return 0;
}

Idea:twh12138

Tutorial is loading...
#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

const int N = 2e5 + 10;

int dis[N];
int n,k;

queue<int> q;

int bfs()
{
    memset(dis,-1,sizeof dis);
    q.push(n);
    dis[n] = 0;
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        if(t == k) return dis[t];
        
        if(t + 1 <= N && dis[t + 1] == -1)
        {
            q.push(t + 1);
            dis[t + 1] = dis[t] + 1;
        }
        if(t - 1 >= 0 && dis[t - 1] == -1)
        {
            q.push(t - 1);
            dis[t - 1] = dis[t] + 1;
        }
        if(t * 2 <= N && dis[2 * t] == -1)
        {
            q.push(2 * t);
            dis[2 * t] = dis[t] + 1;
        }
    }
    
    return 0;
}

int main()
{
    cin >> n >> k;
    cout << bfs() << endl;
}

Idea:CofDoria

Tutorial is loading...
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(l, a, b) for (ll l = a; l < b; ++l)

int t, n;
ll ans = 0;

struct node {
    ll t, val;
    node() { t = 0, val = 0; }
} a[1500005];

bool cmp(node x, node y) {
    if (x.t == y.t) return x.val > y.val;
    return x.t < y.t;
}

priority_queue<int, vector<int>, greater<int> > q;

int main() {
    cin >> n;
    rep(i, 0, n) cin >> a[i].t >> a[i].val;
    sort(a, a + n, cmp);
    rep(i, 0, n) {
        if (i && a[i].t == a[i - 1].t) { 
            if (q.size() < a[i].t) {
                q.push(a[i].val);
                ans += a[i].val;
            } else if (q.top() < a[i].val) {
                ans += a[i].val - q.top();
                q.pop();
                q.push(a[i].val);
            }
        } else {
            ans += a[i].val;
            q.push(a[i].val);
        }
    }
    cout << ans + 5;
    return 0;
}

Idea:lqrs

Tutorial is loading...
#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

#define N 10005
vector<int> edge[N];    //二维数组
int res = 0;

void dfs(int step, int pos, int prepos) {
    if (step == 3) {
        ++res;
        return;
    }
    if (edge[pos].size()) {
        vector<int>::iterator it;
        for (it = edge[pos].begin(); it != edge[pos].end(); ++it)
            if (*it != prepos) dfs(step + 1, *it, pos);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    int n, m, U, V;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> U >> V;
        edge[U].push_back(V);
        edge[V].push_back(U);
    }
    for (int i = 1; i <= n; ++i) dfs(0, i, 0);
    cout << res << endl;
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (0)
| Write comment?