首页 > 其他分享 >杭电多校2023 第三场

杭电多校2023 第三场

时间：2023-07-26 20:33:43浏览次数：43  
标签：pre 杭电多校 cnt ch node int mid 2023 第三场

1005

直接dp即可

#include <bits/stdc++.h>
using namespace std;
int dp[5005][5005];
int N;
int a[5005];
const int MOD = 1e9+7;
int main(){
    int T;
    cin >> T;
    while (T--){
        int N;
        memset(dp,0,sizeof(dp));
        dp[1][1] = 1;
        scanf("%d",&N);
        for (int i = 1 ; i <= N ; i ++){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+N+1);
        for (int i = 2 ; i <= N ; i ++)
            if (a[i] == a[i-1]) dp[i][1] = dp[i-1][1];
            else dp[i][1] = dp[i-1][1]+1;
        for (int i = 2 ; i <= N ; i++)
            for (int j = 2 ; j <= i ; j ++){
                if (i == j) dp[i][j] = dp[i][j-1];
                else if (a[i] == a[i-1]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = (dp[i][j-1]+dp[i-1][j])%MOD;
        }
        for (int i = 1 ; i <= N ; i ++)
            printf("%d\n",dp[N][i]);
    }
    return 0;
}

1011

队友写的，似乎是个大模拟？

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair< int, int > PII;

const int N = 55;

int n, z;
char s[N][N];

int read()
{
    int res = 0, w = 1;
    char ch = getchar();
    while (ch != '-' && !isdigit(ch))
        ch = getchar();
    if (ch == '-')
        w = -1, ch = getchar();
    while (isdigit(ch))
        res = res * 10 + ch - '0', ch = getchar();
    return res * w;
}

void solve()
{
    scanf("%d%d", &n, &z);
    memset(s, 0, sizeof 0);
    for (int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);
        
    //    cout << "---" << endl;
    // for (int i = 1; i <= n; i++)
    // {
    //     for (int j = 1; j <= n; j++)
    //         cout << s[i][j];
    //     cout << endl;
    // }

    if ((n * z) % 100)
    {
        cout << "error" << endl;
        return;
    }

    if (z == 100)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                cout << s[i][j];
            cout << endl;
        }
        return;
    }

    if (z == 125)
    {
        for (int i = 1; i <= n; i += 4)
            for (int j = 1; j <= n; j += 4)
            {
                char ch = s[i][j];
                for (int u = i; u < i + 4; u++)
                    for (int v = j; v < j + 4; v++)
                        if (s[u][v] != ch)
                        {
                            cout << "error" << endl;
                            return;
                        }
            }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j += 4)
            {
                for (int k = 1; k <= 5; k++)
                    cout << s[i][j];
            }
            cout << endl;

            if (i % 4 == 1)
            {
                for (int j = 1; j <= n; j += 4)
                {
                    for (int k = 1; k <= 5; k++)
                        cout << s[i][j];
                }
                cout << endl;
            }
        }
    }

    if (z == 150)
    {
        for (int i = 1; i <= n; i += 2)
            for (int j = 1; j <= n; j += 2)
            {
                char ch = s[i][j];

                for (int u = i; u < i + 2; u++)
                    for (int v = j; v < j + 2; v++)
                        if (s[u][v] != ch)
                        {
                            cout << "error" << endl;
                            return;
                        }
            }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j += 2)
            {
                for (int k = 1; k <= 3; k++)
                    cout << s[i][j];
            }
            cout << endl;

            if (i % 2 == 1)
            {
                for (int j = 1; j <= n; j += 2)
                {
                    for (int k = 1; k <= 3; k++)
                        cout << s[i][j];
                }
                cout << endl;
            }
        }
        return;
    }

    if (z == 175)
    {
        for (int i = 1; i <= n; i += 4)
            for (int j = 1; j <= n; j += 4)
            {
                char ch = s[i][j];

                for (int u = i; u < i + 4; u++)
                    for (int v = j; v < j + 4; v++)
                        if (s[u][v] != ch)
                        {
                            cout << "error" << endl;
                            return;
                        }
            }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j += 4)
            {
                for (int k = 1; k <= 7; k++)
                    cout << s[i][j];
            }
            cout << endl;

            if (i % 4 == 1)
            {
                for (int j = 1; j <= n; j += 4)
                {
                    for (int k = 1; k <= 7; k++)
                        cout << s[i][j];
                }
                cout << endl;
                for (int j = 1; j <= n; j += 4)
                {
                    for (int k = 1; k <= 7; k++)
                        cout << s[i][j];
                }
                cout << endl;
                for (int j = 1; j <= n; j += 4)
                {
                    for (int k = 1; k <= 7; k++)
                        cout << s[i][j];
                }
                cout << endl;
            }
        }
        return;
    }

    if (z == 200)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                for (int k = 1; k <= 2; k++)
                    cout << s[i][j];
            }
            cout << endl;

            for (int j = 1; j <= n; j++)
            {
                for (int k = 1; k <= 2; k++)
                    cout << s[i][j];
            }
            cout << endl;
        }
    }
}

int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }

    return 0;
}

1012


首先，可以把加的过程变成减的过程

然后就会发现这东西和gcd的那个更相减损术非常类似

于是就会考虑在辗转相除法的过程中，记录一下每个数对的情况所能达到的情况，并且排个序

每次查询的时候，就二分一下它在路径上的位置，算一个后缀个数即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 50010;

struct node {
    ll x, y;    
    bool operator < (const node &g) const {
        return x == g.x ? y < g.y : x < g.x;
    }
} ;

map<ll, int> t;

map<node, vector<ll> > pre;

int T, n, q;

ll a[N], b[N];

void gcd(ll x, ll y) {
    if (!x || !y) return ;
    if (x < y) {
        pre[(node){x, y % x}].push_back(y);
        gcd(x, y % x);
    }
    else {
        pre[(node){x % y, y}].push_back(x);
        gcd(x % y, y);
    }
}

int main() {
    scanf("%d", &T);
    for ( ; T; T--) {
        scanf("%d%d", &n, &q);
        t.clear(), pre.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld", &a[i], &b[i]);
            if (a[i] == b[i]) {
                t[a[i]]++;
                continue;    
            }
            gcd(a[i], b[i]);
            if (a[i] < b[i]) pre[(node){a[i], b[i]}].push_back(a[i]);    
            else pre[(node){a[i], b[i]}].push_back(b[i]);    
        }
        for (auto &[u,v]:pre){
            sort(v.begin(),v.end());
        }
        for (int i = 1; i <= q; i++) {
            ll c, d; scanf("%lld%lld", &c, &d);
            int cnt = 0;
            if (c == d) cnt = t[c];
            if (c <= d) {
                node g = (node){c, d % c};
                int siz = pre[g].size();
                int l = lower_bound(pre[g].begin(),pre[g].end(),d)-pre[g].begin();
                /*while (l < r) {
                    int mid = (l + r) >> 1;
                    if (now[mid] < d) l = mid + 1;
                    else r = mid;
                }*/
                cnt += siz - l;
            }
            if (c >= d) {
                node g = (node){c % d, d};
                int siz = pre[g].size();
                /*while (l < r) {
                    int mid = (l + r) >> 1;
                    if (now[mid] < c) l = mid + 1;
                    else r = mid;
                }*/
                int l = lower_bound(pre[g].begin(),pre[g].end(),c)-pre[g].begin();
                cnt += siz - l;
            }
            printf("%d\n", cnt);
        }
    }
    return 0;
}

1004

因为是全随机的数据

所以考虑每一个可能的$\delta X$和 $\delta Y$

随机抽取$100$个可能的值，然后考虑它是否合法

不合法就退出

因为数据全随机，所以其实不合法的概率非常高

#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int T;
int N;
pii a[200005];
map<pii,int> cnt;
int Random(int MOD){
    return 1ll*rand() * 1ll*rand()%MOD*1ll*rand()%MOD;
}
int main(){
    srand(time(NULL));
    cin >> T;
    while (T--){
        cin >> N;
        cnt.clear(); 
        for (int i = 1 ; i <= 2 * N ; i ++){
            cin >> a[i].first >> a[i].second;
            cnt[a[i]] ++;
        }
        vector<pii> ans;
        for (int i = 2 ; i <= 2 * N ; i ++){
            cnt[a[1]] --;
            cnt[a[i]] --;
            int deltaX = a[i].first - a[1].first,deltaY = a[i].second - a[1].second;
            int TT = 1000;
            bool flag = false;
            while (TT --){
                int x = Random(2*N);
                x++;
                if ( x ==1 || x == i) continue;
                //cout << x << endl;
                pii New = {a[x].first + deltaX,a[x].second + deltaY};
                pii New1 ={a[x].first - deltaX,a[x].second - deltaY};
                if (cnt[New] + cnt[New1] < cnt[a[x]]){
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                ans.push_back({deltaX,deltaY});
                ans.push_back({-deltaX,-deltaY});
            }
            cnt[a[1]] ++;
            cnt[a[i]] ++;
        }
        bool flag = false;
        for (int i = 1 ; i <= 2 * N ; i ++)
            if (cnt[a[i]] %2 != 0){
                flag = true;
                break;
            }
        if (flag == false) ans.push_back({0,0});
        sort(ans.begin(),ans.end());
        ans.erase(unique(ans.begin(),ans.end()),ans.end());
        int cntt = 0;
        for (auto v : ans){
            if (flag == true && v.first == 0 && v.second == 0) continue;
            cntt ++;
        }
        cout << cntt << '\n';
        for (auto v : ans){
            if (flag == true && v.first == 0 && v.second == 0) continue;
            cout << v.first << " " << v.second << '\n';
        }
    }
    return 0;
}

 

标签：pre,杭电多校,cnt,ch,node,int,mid,2023,第三场
From： https://www.cnblogs.com/si--nian/p/17583492.html

相关文章

  • 2023牛客多校7.24补题
    J-FineLogic题意：给定n个点和m对偏序关系(x,y)，构造最少的排列数目k，使得在这k个排列中至少有一个排列满足x出现在y的前面。分析：很考验思维的一道题，首先如果m对偏序关系不构成环，也就是一张有向无环图，于是用拓扑排序构造出一个合理排列即可。要是有环，就直接构造两个排列，一个是1<2<.......
  • 2023 暑假集训模拟赛 Day 3
    比赛题目共\(2\)套，其中初赛题\(1\)套，复赛\(2\)题。比赛时间:\(10:50-12:00a.m\)。Part0x01过程-Process\(8:30\,a.m.\)做初赛题目；\(10:40\,a.m.\)拿到题目；\(10:41\,a.m.\)先写\(\text{T1}\)，发现有点像分类讨论；\(10:50\,a.m.\)发现\(\text{T1}\)不需要那......
  • 2023.7.26 周三：instanceof
    1/*2instancof判断两个类之间是否有继承关系3Object->String4Object->Person->Teacher5Object->Person->Student6*/7Objects1=newStudent();8System.out.println(s1instanceofObject);//True9System.out.println(s1instanceofPerson);//T......
  • 2023年7月26日 天气：晴
        今天早上起来背了10个英语单词，然后学习了一个小时的java，写了一会英语阅读，然后和朋友出去打了两个小时的羽毛球，最后写了一会作业。    明天打算看一小时的电视剧，然后和朋友出去玩一会，打一两个小时的篮球，最后晚上练一小时的字，然后学习一小时的java。......
  • NOI 2023 录
    是不是没进集训队不配写回忆录啊，那就摆了吧。Day1我还是难以理解，我是怎样打出100+15+0的好成绩的。也许是因为T1复杂做法调了2.5h才过；也许是因为T2不会找规律也不会正经的dp转移顺序50分m^3暴力还写挂；也许是因为T3从头读错题面到最后也没写出一个正确的低分暴......
  • 行业追踪，2023-07-26，如果主力不骗人，化工原料和磷化工有第一波机会
    自动复盘2023-07-26凡所有相，皆是虚妄。若见诸相非相，即见如来。k线图是最好的老师，每天持续发布板块的rps排名，追踪板块，板块来开仓，板块去清仓，丢弃自以为是的想法，板块去留让市场来告诉你跟踪板块总结：成交额超过100亿排名靠前，macd柱由绿转红成交量要大于均线有必要给每个行......
  • NOI2023 游记
    把前面的复习实况删了，因为实在太摆了！前面在cdqz训了两场模拟赛，垫了两场底！！熟悉了下cdqz键盘，能打。Day0报道日。由于是第一个进去了，被拉着生产了很多照片/采访，开幕式好像重复利用了很多遍这些素材。领到了很多徽章，拉着学弟主动social了很多老哥！！虽然最后还是没有juju......
  • 暑假集训D3 2023.7.26 补题
    G.P6183[USACO10MAR]TheRockGameS题意:给定长度n,构造\(2^n\)个由X和O组成的字符串,使得第一个字符串和最后一个字符串只由O组成,并且相邻的字符串只有一处不同,不得有重复的字符串.BFS貌似做不了.看题解有佬用格雷码的知识.代码如下#include<stdio.h>#include<st......
  • 设计师2023常用的协同设计工具推荐
    组织结构越来越复杂，团队中的每个人都有独特的技能、经验和专业知识。我们怎样才能让团队更好地合作？在这种情况下，协同设计应运而生。UI的未来是协同设计！如果你想把握未来的设计趋势，不妨从使用高效的协同设计软件开始！本文帮助您盘点10款适合UI/UX设计师的协同设计软件1.即时设......
  • 20230726
    复赛完全背包定义：有n种物品和一个容量为v的背包，第i种物品体积为c[i]，价值为w[i]，每种物品有无穷件，问如何选取物品放入背包，可使价值总和最大。与01背包的区别：01背包一个物品只能选一件，而完全背包一个物品可以选多件例题时间：1s空间：128M题目描述：一个旅行者有一个最......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99