首页 > 其他分享 >winter 2024 day3

winter 2024 day3

时间：2024-01-25 13:33:48浏览次数：36  
标签：typedef const winter int double day3 long 2024 define

SMU Winter 2024 round 1

AB. Sum of Medians

思路：贪心的想，只有中位数有贡献，并且知道了中位数的位置以及中位数左边的数的个数 l 和中位数右边的数的个数 r ，那么对于一个不递减的数组，要取出最大的中位数，即取出l个最小的数和r个最大的数，中位数即为第r+1大的数。直到数取完为止。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;


void solve() {
    int n,k;cin>>n>>k;
    vector<int>ve(n*k+1);
    for(int i=1;i<=n*k;++i)cin>>ve[i];
    int ans=0;
    int rc=n/2,lc=n-rc-1;
    int l=1,r=n*k;
    while(r-l+1>=n){
        ans+=ve[r-rc];
        r-=rc+1;
        l+=lc;
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

BB. Repainting Street

思路：由于c的范围很小，直接暴力枚举每一种c需要的粉刷次数

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;


void solve() {
    int n,k;cin>>n>>k;
    vector<int>ve(n);
    set<int>se;
    for(int i=0;i<n;++i){
        cin>>ve[i];
        se.insert(ve[i]);
    }
    int ans=INF;
    for(auto v:se){
        int cnt=0;
        for(int i=0;i<n;++i){
            if(ve[i]!=v)cnt++,i+=k-1;
        }
        ans=min(ans,cnt);
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

CJ. Let's Play Jigsaw Puzzles!

思路：由于每个数的四个方向上的数都知道，那么找出左上角的数即可一行行枚举推出。也可以bfs或者dfs

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void solve() {
    int n;cin>>n;
    int m=n*n;
    vector<vector<int>>ve(m+1,vector<int>(4));
    int s;
    for(int i=1;i<=m;++i){
        for(int j=0;j<4;++j){
            cin>>ve[i][j];
        }
        if(ve[i][0]==-1&&ve[i][2]==-1)s=i;
    }
    vector<vector<int>>g(n+1,vector<int>(n+1));
    vector<vector<int>>st(n+1,vector<int>(n+1));
    g[1][1]=s;
    queue<PII>q;
    q.push({1,1});
    st[1][1]=1;
    while(q.size()){
        auto t=q.front();q.pop();
        for(int i=0;i<4;++i){
            if(ve[g[t.first][t.second]][i]==-1)continue;
            int xx=t.first+dx[i],yy=t.second+dy[i],id=ve[g[t.first][t.second]][i];
            if(!st[xx][yy]){
                st[xx][yy]=1;
                g[xx][yy]=id;
                q.push({xx,yy});
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cout<<g[i][j];
            if(j!=n)cout<<' ';
        }
        cout<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

DC. Bouncing Ball

思路：也是暴力枚举删除个数，由于k是不变的，那每个位置对应跳到的位置也是不变的，即用位置%k对它们进行分类，可以预处理出从每个位置开始跳后的用时

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;


void solve() {
    int n,p,k;cin>>n>>p>>k;
    string s;cin>>s;
    int x,y;cin>>x>>y;
    int ans=INT32_MAX;
    vector<int>g(k+5);
    for(int i=0;i<s.size();++i){
        if(i+1>=p&&s[i]=='0')g[i%k]++;
    }
    for(int i=0,st=p-1;i<n&&st<n;++i,st++){
        int cnt=i*y+g[st%k]*x;
        ans=min(ans,cnt);
        g[st%k]-=s[st]=='0';
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

EC1. Binary Table (Easy Version)

思路：同下题

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;
int dx[10]={-1,-1,0,1,1,1,0,-1,0};
int dy[10]={0,1,1,1,0,-1,-1,-1,0};
int d[17][3]={{},{0,6,7},{0,7,8},{0,6,8},{6,7,8},
              {0,1,8},{0,1,2},{1,2,8},{0,2,8},
              {5,6,8},{4,6,8},{4,5,8},{4,5,6},
              {2,4,8},{2,3,8},{2,3,4},{3,4,8}};
void solve() {
    int n,m;
    cin>>n>>m;
    vector<vector<int>>ve(n+5,vector<int>(m+5));
    for(int i=1;i<=n;++i){
        string s;
        cin>>s;
        for(int j=1;j<=m;++j){
            ve[i][j]=s[j-1]-'0';
        }
    }
    vector<vector<PII>>ans;
    auto add=[&](int x,int y,int p){
        vector<PII>t;
        for(int i=0;i<3;++i){
            int xx=x+dx[d[p][i]],yy=y+dy[d[p][i]];
            ve[xx][yy]^=1;
            t.push_back({xx,yy});
        }
        ans.push_back(t);
    };
    if(n%2){
        for(int i=1;i<m;++i)
            if(ve[n][i]==1)add(n,i,5);
        if(ve[n][m]==1)add(n,m,2);
    }
    if(m%2){
        if(ve[1][m]==1)add(1,m,9);
        for(int i=2;i<n;++i)
            if(ve[i][m]==1)add(i,m,4);
        if(ve[n][m]==1)add(n,m,4);
    }
    auto sum=[&](int x,int y){
        return ve[x][y]+ve[x][y-1]+ve[x-1][y]+ve[x-1][y-1];
    };
    auto to3=[&](int x,int y){
        if(ve[x][y]==0)add(x,y,1);
        else if(ve[x-1][y]==0)add(x,y,4);
        else if(ve[x][y-1]==0)add(x,y,2);
        else add(x,y,3);
    };
    auto to2=[&](int x,int y){
        if(ve[x][y]==1&&ve[x-1][y]==1)add(x,y,4);
        else if(ve[x-1][y-1]==1&&ve[x][y-1]==1)add(x,y,2);
        else if(ve[x-1][y-1]==1&&ve[x-1][y]==1)add(x,y,3);
        else if(ve[x][y-1]==1&&ve[x][y]==1)add(x,y,2);
        else if(ve[x-1][y-1]==1&&ve[x][y]==1)add(x,y,3);
        else if(ve[x][y-1]==1&&ve[x-1][y]==1)add(x,y,2);
        to3(x,y);
    };
    auto to1=[&](int x,int y){
        if(ve[x][y]==1)add(x,y,3);
        else if(ve[x][y-1]==1)add(x,y,4);
        else if(ve[x-1][y]==1)add(x,y,2);
        else add(x,y,1);
        to2(x,y);
    };
    auto to4=[&](int x,int y){
        add(x,y,3);
        to1(x,y);
    };
    for(int i=2;i<=n;i+=2){
        for(int j=2;j<=m;j+=2){
            int c=sum(i,j);
            if(c==4)to4(i,j);
            else if(c==3)to3(i,j);
            else if(c==2)to2(i,j);
            else if(c==1)to1(i,j);
        }
    }
    cout<<ans.size()<<'\n';
    for(auto v:ans){
        for(int i=0;i<3;++i){
            cout<<v[i].first<<' '<<v[i].second;
            if(i!=2)cout<<' ';
        }
        cout<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

FC2. Binary Table (Hard Version)

思路：模拟。可以只看大小为4的正方形的情况，发现正方形的所有情况都可以在不超过4次操作变成全0。对于n或m为奇数时，对最后一行或一列直接操作变成0就好，次数平均每个格子一次

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;
int dx[10]={-1,-1,0,1,1,1,0,-1,0};
int dy[10]={0,1,1,1,0,-1,-1,-1,0};
int d[17][3]={{},{0,6,7},{0,7,8},{0,6,8},{6,7,8},
              {0,1,8},{0,1,2},{1,2,8},{0,2,8},
              {5,6,8},{4,6,8},{4,5,8},{4,5,6},
              {2,4,8},{2,3,8},{2,3,4},{3,4,8}};
void solve() {
    int n,m;
    cin>>n>>m;
    vector<vector<int>>ve(n+5,vector<int>(m+5));
    for(int i=1;i<=n;++i){
        string s;
        cin>>s;
        for(int j=1;j<=m;++j){
            ve[i][j]=s[j-1]-'0';
        }
    }
    vector<vector<PII>>ans;
    auto add=[&](int x,int y,int p){
        vector<PII>t;
        for(int i=0;i<3;++i){
            int xx=x+dx[d[p][i]],yy=y+dy[d[p][i]];
            ve[xx][yy]^=1;
            t.push_back({xx,yy});
        }
        ans.push_back(t);
    };
    if(n%2){
        for(int i=1;i<m;++i)
            if(ve[n][i]==1)add(n,i,5);
        if(ve[n][m]==1)add(n,m,2);
    }
    if(m%2){
        if(ve[1][m]==1)add(1,m,9);
        for(int i=2;i<n;++i)
            if(ve[i][m]==1)add(i,m,4);
        if(ve[n][m]==1)add(n,m,4);
    }
    auto sum=[&](int x,int y){
        return ve[x][y]+ve[x][y-1]+ve[x-1][y]+ve[x-1][y-1];
    };
    auto to3=[&](int x,int y){
        if(ve[x][y]==0)add(x,y,1);
        else if(ve[x-1][y]==0)add(x,y,4);
        else if(ve[x][y-1]==0)add(x,y,2);
        else add(x,y,3);
    };
    auto to2=[&](int x,int y){
        if(ve[x][y]==1&&ve[x-1][y]==1)add(x,y,4);
        else if(ve[x-1][y-1]==1&&ve[x][y-1]==1)add(x,y,2);
        else if(ve[x-1][y-1]==1&&ve[x-1][y]==1)add(x,y,3);
        else if(ve[x][y-1]==1&&ve[x][y]==1)add(x,y,2);
        else if(ve[x-1][y-1]==1&&ve[x][y]==1)add(x,y,3);
        else if(ve[x][y-1]==1&&ve[x-1][y]==1)add(x,y,2);
        to3(x,y);
    };
    auto to1=[&](int x,int y){
        if(ve[x][y]==1)add(x,y,3);
        else if(ve[x][y-1]==1)add(x,y,4);
        else if(ve[x-1][y]==1)add(x,y,2);
        else add(x,y,1);
        to2(x,y);
    };
    auto to4=[&](int x,int y){
        add(x,y,3);
        to1(x,y);
    };
    for(int i=2;i<=n;i+=2){
        for(int j=2;j<=m;j+=2){
            int c=sum(i,j);
            if(c==4)to4(i,j);
            else if(c==3)to3(i,j);
            else if(c==2)to2(i,j);
            else if(c==1)to1(i,j);
        }
    }
    cout<<ans.size()<<'\n';
    for(auto v:ans){
        for(int i=0;i<3;++i){
            cout<<v[i].first<<' '<<v[i].second;
            if(i!=2)cout<<' ';
        }
        cout<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

GD. Walker

思路：

 

HM. Gitignore

思路：将不能忽略的所有文件路径用哈希表存储，对于要忽略的，遍历其路径，直到当前找到的文件夹名不在不能忽略的哈希表存储中，若该文件夹名已在忽略名单中，则直接跳过；若不在则将其加入忽略名单，并且答案加一；

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

void solve() {
    int n,m;cin>>n>>m;
    vector<string>a(n),b(m);
    for(int i=0;i<n;++i)cin>>a[i];
    for(int i=0;i<m;++i)cin>>b[i];
    map<string,int>mp;
    for(int i=0;i<m;++i){
        string c;
        for(int j=0;j<b[i].size();++j){
            c.push_back(b[i][j]);
            if(b[i][j]=='/'){
                mp[c]=1;
            }
        }
        mp[c]=1;
    }
    int ans=0;
    for(int i=0;i<n;++i){
        string c;
        bool ok=false;
        for(int j=0;j<a[i].size();++j){
            c.push_back(a[i][j]);
            if(a[i][j]=='/'){
                if(!mp.count(c))mp[c]=2,ans++;
                if(mp[c]==1)continue;
                ok=true;
                break;
            }
        }
        if(!ok&&mp[c]!=2)ans++;
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

IC. Engineer Artem

思路：一个数要与四个方向上的数不同，对矩阵整体来看，其实可以分成两批，在同一批的数可以相同，那么可以想到奇偶性，把两批的数分别变成同批同奇偶性即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

void solve() {
    int n,m;cin>>n>>m;
    vector<vector<int>>ve(n+1,vector<int>(m+1));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>ve[i][j];
            if(i%2){
                if(j%2&&ve[i][j]%2==0)ve[i][j]++;
                else if(j%2==0&&ve[i][j]%2)ve[i][j]++;
            }else{
                if(j%2&&ve[i][j]%2)ve[i][j]++;
                else if(j%2==0&&ve[i][j]%2==0)ve[i][j]++;
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j){
            cout<<ve[i][j];
            if(j!=m)cout<<' ';
        }cout<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

JD. Good Triple

思路：可以打表看看，发现没有找到满足条件的情况的长度一定不超过8，那么对于每个l，暴力找出最小的r即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;
void solve() {
    string s;
    cin>>s;
    int n=s.size();
    s=' '+s;
    int ans=0;
    for(int l=1,r=l+2;r<=n;++l){
        bool ok=false;
        while(r<=n){
            for(int d=1;l+2*d<=r;++d){//间距
                for(int st=l;st+2*d<=r;++st)//起点
                {
                    if(s[st]==s[st+d]&&s[st]==s[st+2*d]){
                        ok=true;break;
                    }
                }
                if(ok&&r<=n){
                    ans+=n-r+1;
                    break;
                }
            }
            if(ok)break;
            r++;
        }
    }
    cout<<ans;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

 

 

标签：typedef,const,winter,int,double,day3,long,2024,define
From： https://www.cnblogs.com/bible-/p/17986960

相关文章

  • 如何手工制作绿色免安装单文件同花顺免费版Windows客户端 2024-01-25
    如何手工制作绿色免安装单文件同花顺免费版Windows客户端  2024-01-25第1步、下载同花顺免费版http://download.10jqka.com.cn/第2步、安装同花顺免费版第3步、移动同花顺免费版软件到文件夹 D:\Prog\同花顺第4步、新建批处理脚本文件 D:\Prog\同花顺\一键打包\一键打......
  • 2024,管理企业一定要做的动作。
    2024年推行OKR对企业的好处一、背景介绍随着市场竞争的日益激烈，企业需要更加高效的目标管理方法来推动团队发展和提高业绩。OKR（ObjectivesandKeyResults）作为一种先进的目标管理工具，在许多成功企业中得到了广泛应用。本文将探讨在2024年推行OKR对企业的好处。二、提高目标一......
  • 2024-1-25HTTP协议 - 请求报文
    目录HTTP协议-请求报文HTTP协议-请求报文HTTP协议：规定了浏览器发送及服务器返回内容的格式请求报文：浏览器按照HTTP协议要求的格式，发送给服务器的内容总结：1.浏览器发送给服务器的内容叫做请求报文2.请求报文的组成3.查看请求报文......
  • 2024-1-25axios错误处理
    目录axios错误处理axios错误处理该错误是当时在POST案例出现的，当提交过一次用户后再次提交出现了报错。场景：再次注册相同的账号，会遇到错误信息处理：用更直观的方式，给普通用户展示错误信息错误处理固定格式语法：在then方法的后面，通过点语法调用catch方法，传入回调函数error并定......
  • 云计算学习day3
    学习了Linus系统中vim命令的用法vim为创建文本/编辑文本命令（类似于word）输入vim+空格+文件名后即可创建/编辑文件点击i键即可进行编辑编辑完成后点击esc键输入：（英文）输入指令wq即可保存退出w为保存、q为退出、！为强制执行又应用vim编辑虚拟机程序使Xshell7可以连接虚拟机首......
  • 2024-1-25常见请求方法和数据提交
    目录常见请求方法和数据提交常见请求方法axios请求配置这里提供一个案例来学习addEventListener方法总结常见请求方法和数据提交常见请求方法什么是请求方法请求方法：对服务器资源，要执行的操作请求方法操作GET获取数据POST提交数据PUT修改数据（全部）DELETE......
  • 2024AAAI_SGNet Structure Guided Network via Gradient-Frequency Awareness for Dep
    1.任务描述: 给定输入LR深度图和HRRGB图像，引导DSR目的是在ground-truth深度图监督的条件下，预测HR深度图2.Network本文提出的SGNet主要包括两部分，即梯度校准模块(GCM)和频率感知模块（FAM）。首先将RGB图像和上采样后的LR深度图送入到GCM，利用RGB丰富的梯度信息在梯度域中......
  • C语言基础-表达式-day3
    一、表达式一个表达式是一系列运算符和算子的组合，用来计算一个值运算符是指进行运算的动作，比如加法运算符+，减法运算符-算子是指参与运算的值，这个值可能常数，也可能是变量，还可能是一个方法的返回值1、计算时间差#include<stdio.h>intmain(){inthour1,minute1;......
  • 2024/1/24 算法笔记
    1.快速幂模板虽然前面可能写过了，但是遇到了就再贴一下。LLqmi(LLa,LLk,LLp){LLres=1%p;while(k){if(k&1)res=res*a%p;a=a*a%p;k=k>>1;}returnres;}2.最大子段和给一个数组，求其中元素总和最大......
  • SNOI 2024 题解（坑：D1T3 D2T1 D2T2）
    树V图相同\(f(i)\)的点必然构成一个连通块，不然一定无解。每一个连通块中需要选出一个关键点，考虑相邻连通块是否合法，发现条件其实很很好判，就是两个交界点的距离需要满足某个大小关系，容易预处理后\(O(1)\)判，于是\(f_{u,x}\)表示\(u\)连通块内取\(x\)的方案数，DP即可。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99