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

2023杭电多校第二场

时间：2023-07-20 19:22:06浏览次数：39  
标签：杭电多校 return 第二场 int 2023 cin -- ans include

1001

求个SG然后打表

发现$SG=0$的点满足$t = k_1 * (4*K+2) + (K+1)$

#include <bits/stdc++.h>
using namespace std;
int T,N;
int main(){
    cin >> T;
    while (T--){
        int N,K;
        cin >> K >> N;
        if (N <= K) cout << "Alice\n";
        else if (N%(4*K+2) == K+1) cout << "Bob\n";
        else cout << "Alice\n";
    }
    return 0;
}

附带打表代码.jpg

#include <bits/stdc++.h>
using namespace std;
int K;
bool bk[50005];
long long sg[50005];
vector<int> nw;
int SG(int N){
    if (sg[N]!=-1) return sg[N]; 
    if (N == K+1) return 0;
    if (N == 0) return 0; 
    if (N <= K) return 1;
    nw.clear();
    for (int i = 1 ; i <= N-K-1 ; i ++){
        int sgn = SG(i) ^ SG(N-K-i);
        nw.push_back(sgn); 
    }
    sort(nw.begin(),nw.end());
    for (int i = 0 ; i < 500 ; i ++){
        bk[i] = false;
    }
    for (auto v : nw)
        bk[v] = true;
    for (int i = 0 ; i < 500 ; i ++){
        if (!bk[i]) return sg[N] = i;
    }
}
int main(){
    memset(sg,-1,sizeof(sg));
    int N;
    K = 2;
    for (int i = 1 ; i <= 50 ; i ++)
        if (SG(i) == 0) cout << i << endl;
    return 0;
}

1002

分类讨论，把连续的1和0分别压成一段进行考虑即可。

#include <bits/stdc++.h>
using namespace std;
int T;
char a[100005];
struct Node{
    int Len;
    int Type;
};
vector<Node> nw;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    cin >> T;
    while (T--){
        int N;
        long long K;
        cin >> N >> K;
        bool flag = false;
        int cnt = 0;
        cin >> a[1];
        cnt = 1;
        nw.clear();
        for (int i = 2 ; i <= N ; i++){
            cin >> a[i];
            if (a[i] == '0') flag = true; 
            if (a[i] == a[i-1]) cnt ++;
            else{
                nw.push_back(Node{cnt,a[i-1] - '0'});
                cnt = 1;
            }
        }
        if (N == 1){
            int t = K%2;
            cout <<1-t;
            cout << endl;
            continue;
        }
        if (!flag){
            for (int i = 1 ; i < N ; i ++)
                cout << a[i];
            if(K==1) cout << 0;
            else cout << 1;
            cout << endl;
            continue;
        }
        nw.push_back(Node{cnt,a[N]-'0'});
        int Len = nw.size();
        for (int i = 0 ; i < Len ; i ++){
            if (nw[i].Type == 0 && K > 0){
                K--;
                nw[i].Type = 1;
            }
        }
        for (int i = 0 ;i < Len-1 ; i ++){
            for (int j = 0 ; j < nw[i].Len ; j ++)
                cout << nw[i].Type;
        }
        for (int i = 0 ;i < nw[Len-1].Len - 1;i++){
            cout << nw[Len-1].Type;
        }
        long long t = K%2;
        t = 1ll - t; 
        cout << nw[Len-1].Type;
        cout << endl;
    }
    return 0;
}

1004

队友写的签到，咕咕

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long LL;

const LL mod = 998244353;

LL n;
LL ans;

LL qmi(LL a, LL k)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    
    while(T --)
    {
        scanf("%lld", &n);
        ans = 1;
//        for(int i = 3; i <= n; i ++)
//            ans = (ans * 2 + 1) % mod;
        if(n >= 3) ans = qmi(2, n - 1) - 1;
        printf("%lld\n", (ans % mod + mod) % mod);
    }    
    
    return 0;
}

1007

枚举中间和底下两个点

问题转化成两个东西的共同出边点

邻接矩阵存图，bitset取个出边的$and$即可

然后组合数一下，从共同出点选$4$个，其余点选$2$个

如果上点和下点连边，记得把其余点的个数-1

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1000000007;
bitset<1005> a[1005];
int d[1005];
int fac[1005],inv[1005];
int C(int n,int r){
    return fac[n] * inv[r] % MOD * inv[n-r]%MOD;
}
int Pow(int x,int y){
    int ans = 1;
    for (;y;y>>=1){
        if (y & 1) ans = 1ll *ans * x %MOD;
        x = 1ll * x * x %MOD;
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    fac[0] = 1;
    int T;
    cin >> T;
    for (int i = 1 ; i <= 1000 ; i ++)
        fac[i] = 1ll * fac[i-1] * i %MOD;
    inv[1000] = Pow(fac[1000],MOD-2);
    for (int i = 999 ; i >= 1 ; i --)
        inv[i] = 1ll*inv[i+1]*(i+1)%MOD; 
    inv[0] = 1;
    while (T--){
        int N,M;
        cin >> N >> M;
        memset(d,0,sizeof(d));
        for (int i = 1 ; i <= N ; i ++)
            a[i].reset();
        for (int i =1 ; i <= M ; i ++){
            int u,v;
            cin >> u >> v;
            a[u].set(v,1);
            a[v].set(u,1);
            d[u] ++;
            d[v] ++; 
        }
        int ans = 0;
        for (int i = 1 ; i <= N ; i ++){
            for (int j = 1 ; j <= N ; j ++){
                if ( i == j) continue;
                bitset<1005> s;
                s = a[i] & a[j];
                int t = s.count();
                if (t < 4) continue;
                if (d[i] < 6) continue;
                int tt = d[i] - 4;
                if (a[i][j] == 1) tt --;
                ans = (ans + 1ll * C(t,4) * C(tt,2) %MOD)%MOD;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

1009

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1000010;

char s[N];

int main()
{
    int T;
    scanf("%d", &T);
    
    while(T --)
    {
        scanf("%s", s);
        int n = strlen(s);
        
        int ans = 0;
        for(int i = 1; i < n;i ++)
        {
            if(s[i] == s[i - 1]) ans ++;
        }
        
        printf("%d\n", ans);
    }    
    
    return 0;
}

队友写的签到

1010

根据数据范围不难猜测应该可以$O(NM)$的dp，但是空间存不下

我的想法大概是$f[i][j]$表示最后一个1在$i$号点，上一个$1$和它的距离为$j$

转移随便写写，会发现可以用后缀$min$优化一下

然后会发现其实只有距离为$m$以下的那些信息是有意义的，滚动一下dp数组就好了，变成$m*m$，足以通过

然后喂给队友之后他似乎改了改我的状态表示，不过过了(

代码是队友写的，做法类似，但是他拉了个单调栈维护后缀min

#include <iostream>
#include <list>
#include <cstring>
using namespace std;

const int N = 2e4 + 5;
const int M = 2e3 + 5;
const int INF = 0x3f3f3f3f;

struct D {
    int p, v;
};

int n, m;
int a[N];
list<D> stk[N];

void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        stk[i].clear();
    }
    if (n == m) {
        int Min1 = INF;
        int Min2 = INF;
        for (int i = 1; i <= n; i++) {
            if (a[i] <= Min1) {
                Min2 = Min1;
                Min1 = a[i];
            } else if (a[i] < Min2) {
                Min2 = a[i];
            }
        }
        printf("%d\n", Min1 + Min2);
        return;
    }
    int ans = INF;
    for (int i = 2; i <= n; i++) {
        for (int j = i - 1, e = max(i - m + 1, 1); j >= e; j--) {
            if (i <= m) {
                int k = a[i] + a[j];
                if (stk[i].empty() || k < stk[i].back().v) {
                    stk[i].push_back((D){j, k});
                }
                if (i >= n - m + 2 && j >= n - m + 1) {
                    ans = min(ans, k);
                }
                continue;
            }
            if (stk[j].empty()) {
                continue;
            }
            int res = a[i] + stk[j].back().v;
            if (stk[j].back().p == i - m) {
                stk[j].pop_back();
            }
            if (stk[i].empty() || res < stk[i].back().v) {
                stk[i].push_back((D){j, res});
            }
            if (i >= n - m + 2 && j >= n - m + 1) {
                ans = min(ans, res);
            }
        }
    }
    printf("%d\n", ans);
}

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

 

标签：杭电多校,return,第二场,int,2023,cin,--,ans,include
From： https://www.cnblogs.com/si--nian/p/17569435.html

相关文章

  • 2023年7月20日 天气：晴
       今天早上起来背了10个单词，然后出去打了两个小时的羽毛球，然后看了一小时的电视剧，再就是练了一个小时的字，然后学习了一个小时的java，最后看了一会儿构建之法，编程了一个小时的C语言。  明天打算早上起来看一小时的英语课本，然后出去玩一个小时，再看一小时的java课本，然后练......
  • 《渗透测试》Day1 WEB攻防-前后台功能点&文件下载&文件读取&文件删除&目录遍历&目录穿
     #文件安全-下载&删除-黑白盒1、下载=读取常规下载URL：http://www.xiaodi8.com/upload/123.pdf可能存在安全URL：http://www.xiaodi8.com/xx.xx?file=123.pdf利用：常规下载敏感文件（数据库配置，中间件配置，系统密匙等文件信息）2、文件删除（常出现后台中）可能存在安全问题：前台或后台......
  • 2023-7-19
    19：信息收集（昨天下午和晚上弄靶场来着，上午随便写了点）呃……这个发博客好像不太好贴点网址看看吧主动与被动信息搜集：https://zhuanlan.zhihu.com/p/567027661?utm_id=0https://www.blog.23day.site/articles/74https://blog.51cto.com/summer1/5827662也就那些，差不了太多g......
  • 2023.7.20 环形子数组的最大和
    求子数组最大和可以用dp解决，所以环形子数组也可以用dp解决。最简单的就是破环成链，将原数组再复制一遍然后接到尾端，然后对每个起点做一次求子数组最大和dp。但是由于n的范围较大，这样做的时间复杂度是\(n^2\)，会超时。所以必须想办法优化。根据这张图，我们可以把子数组分为二种情......
  • 2023牛客多校7.17补题
    当时就做了两道签到题DJ，这两天补了四道简单题HKLMD-Chocolate题意：\(n×m\)的巧克力，Kelin先手，WalkAlone后手，每人每次拿走一块左下角为\((1,1)\)的子矩形的巧克力，谁拿走\((n,m)\)处的巧克力谁输。分析：这是一道结论题，只有\(1×1\)的时候后手赢，其余情况下都是先手赢。证明......
  • 【日记】2023年7月20日
    2023年7月20日晴日程安排：八点半之前到达公司，吃点早饭开始今天的学习，继续学习昨天的文档和芯片的内容。   学习内容：芯片的分类本文重点关注芯片中晶体管工作状态和电信号种类，把芯片家族粗略划分为：数字电路芯片模拟电路芯片数模混合电路芯片特种电路芯片......
  • 20230719-动态规划DP
    20230719数位DPP4127[AHOI2009]同类分布题目描述传送门求出[a,b]中各位数字之和能整除原数的数的个数\(a,b≤1e18\)Solution对于这种求是否能整除的题我们只有在最后才能得到答案这道题很明显是数位DP考虑用记忆化搜索来实现对于每一位我们需要维护前面的数字之......
  • 在2023.7.20发生的一些事
    去Luogu交了一篇题解，其中关于有\(n\)层的满二叉树有一共有多少个节点的内容，一开始看错了写的是\(n^2\)，审核打回说是\(2^n\)，然后我又改成\(2^n\)，结构审核又打回来说是\(2^n-1\)。虽然有我自己概念不清的原因在但是还是感觉有点无语(ˉ▽ˉ；).........
  • 【禅道2023年中总结】用热爱，走一些“远”路！
    相伴：开源十四载，更适合成长中企业的项目管理工具盛夏来临，2023年也过去了一半。回顾上半年，禅道团队不断突破，拥抱变化，迎接新的机遇和挑战，一些来之不易的突破，让我们惊叹、思考或感动……时光的车轮滚滚向前，14岁的禅道青春正好。这十余年间，虽然历经过波折与磨难，禅道却依然保持着顽强的......
  • 2023 睿抗机器人开发者大赛CAIP-编程技能赛-本科组（省赛）记录
    RC-u1亚运奖牌榜思路略代码点击查看代码#include<bits/stdc++.h>#definerep(i,x,y)for(inti=x;i<=y;++i)usingnamespacestd;#defineintlonglonginta[30][30];signedmain(){ intn; cin>>n; while(n--){ intx,c; cin>>x>>c; a[x]......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99