首页 > 其他分享 >2024杭电多校第七场

2024杭电多校第七场

时间：2024-08-10 17:16:38浏览次数：7  
标签：杭电多校 ch return int res void 第七场 long 2024

1004

如果r2>2r1且树的直径>2r1，则逃跑方总能逃跑

否则攻击方肯定能一步步把其逼到叶子节点

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,s,r1,r2;
vector<int> ver[N+5];
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
int dep[N+5],q[N+5],l,r;
int bfs(int st)
{
    int res=st;
    for(int i=1;i<=n;++i) dep[i]=0;
    q[l=r=1]=st,dep[st]=1;
    for(int x;l<=r;)
    {
        x=q[l++];
        if(dep[x]>dep[res]) res=x;
        for(auto y:ver[x])
        {
            if(dep[y]) continue;
            dep[y]=dep[x]+1,q[++r]=y;
        }
    }
    return res;
}
void Kafka()
{
    n=read(),s=read(),r1=read(),r2=read();
    for(int i=1;i<=n;++i) ver[i].clear();
    for(int i=1;i<n;++i)
    {
        int u=read(),v=read();
        ver[u].push_back(v);
        ver[v].push_back(u);
    }
    if(r2<=r1*2) {puts("Kangaroo_Splay");return;}
    int d=dep[bfs(bfs(s))]-1;
    if(d<=r1*2) {puts("Kangaroo_Splay");return;}
    puts("General_Kangaroo");
}
signed main()
{
    for(int T=read();T--;)Kafka();
    return 0;
}

 

1007

考虑比较裸的线段树优化dp，优化后dp[ a[i] ]为max(dp[ a[i]-k ],dp[ a[i]+k ])+1

这样的时间复杂度是O(q*n*log)的

再考虑怎么优化这个事情，其实决策点并没有一个范围这么大，而是[ a[i]-k,a[i] ]中下标最靠后的点(反证法)

预处理出每个点可以从哪两个点转移

时间复杂度是O(nlogn+nq)

#include<bits/stdc++.h>
using namespace std;
#define L (p<<1)
#define R ((p<<1)|1)
#define Mid (l+r>>1)
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
const int N=1e5+505;
long long n,m,k,q;
long long a[N];
int l[N],r[N];
map<long long,int> f;
struct BIT{
    int t[N*4];
    void up(int p){
        t[p]=max(t[L],t[R]);
    }
    void build(int p,int l,int r){
        if (l==r){
            t[p]=0;
            return;
        }
        int mid=Mid;
        build(L,l,mid);
        build(R,mid+1,r);
        t[p]=t[L]=t[R]=0;
    }
    void change(int p,int l,int r,int x,int w){
        if (l==r){
            t[p]=w;
            //printf("t[%d]=%d l=%d r=%d x=%d w=%d\n",p,t[p],l,r,x,w);
            return;
        }
        int mid=Mid;
        if (x<=mid) change(L,l,mid,x,w);
            else change(R,mid+1,r,x,w);
        up(p);
        
    }
    int find(int p,int l,int r,int x,int y){
        if (l>=x&&r<=y){
            return t[p];
        }
        int mid=Mid;
        int res=0;
        if (x<=mid) res=max(res,find(L,l,mid,x,min(mid,y)));
        if (y>mid) res=max(res,find(R,mid+1,r,max(mid+1,x),y));
        return res;
    }
}t;
void test_tree(){
    //for (int i=1;i<=10;i++)
        //printf("t[%d]=%d\n",i,t.t[i]);
    for (int i=1;i<=n;i++)
        printf("dp[%d]=%d\n",i,t.find(1,1,n,i,i));
}
int query(int x,int y){
    t.build(1,1,n);
    int res;
    for (int i=x;i<=y;i++){
        if (l[i]>=r[i]) res=0;
            else res=t.find(1,1,n,l[i],r[i]-1);
        //test_tree();
        //printf("l[i]=%d r[i]-1=%d res=%d\n",l[i],r[i]-1,res);
        t.change(1,1,n,f[a[i]],res+1);
        
    }
    res=t.find(1,1,n,1,n);
    return res;
}
void test(){
    for (int i=1;i<=n;i++)
        cout << l[i] << "      " << r[i] << endl;
}
void work(){
    cin >> n >> m >> k;
    f.clear();
    for (int i=1;i<=n;i++){
        cin >> a[i];
        f[a[i]]=0;
    }
    int cnt=0;
    for (auto i=f.begin();i!=f.end();i++)
        i->second=++cnt;
    for (int i=1;i<=n;i++){
        l[i]=distance(f.begin(),f.lower_bound(a[i]-k))+1;
        r[i]=distance(f.begin(),f.upper_bound(a[i]+k))+1;
    }
    //test();    
    cin >> q;
    for (int i=1;i<=q;i++){
        int x,y;
        cin >> x >> y;
        cout << y-x+1-query(x,y) << endl;
    }
}
signed main()
{    
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin >> T;
    while(T--) work();
    return 0;
}

 

1009

树dp完后取代价最大的孩子节点ban掉，实现起来主要注意会不会爆longlong

小技巧是和一个比较大的常数取min

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
const __int128 inf = 2e9+10;
int n,k;
__int128 t[N],num[N],ans[N];
vector<int>e[N];
void dfs(int u,int p){
    if(e[u].size()==0){
        ans[u]=t[u];
        return;
    }
    ans[u]=0;// needed time
    for(auto v:e[u]){
        if(v==p) continue;
        //cout<<u<<" to "<<v<<"\n";
        dfs(v,u);
        ans[u]+=num[v]*ans[v];
        ans[u]=min(ans[u],inf);
    }
}
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        t[i]=num[i]=0;
        e[i].clear();
    }
    for(int i=1;i<=n;i++) {
        int op;cin>>op;
        if(op==0) {
            int x;cin>>x;
            t[i]=x;
        }
        else {
            int tot;cin>>tot;
            for(int j=1;j<=tot;j++){
                int x,a;cin>>x>>a;
                num[a]=x;
                e[i].push_back(a);
            //    cout<<i<<" -> "<<a<<"\n";    
            }
        }
    }
    dfs(k,0);
    __int128 mx=0;
    int pos=-1;
    for(auto v:e[k]){
        if(num[v]*ans[v]>mx){
            pos=v;
            mx=num[v]*ans[v];
        }
    }
    
    __int128 out=0;
    for(auto v:e[k]){
        if(v==pos) continue;
        out=out+num[v]*ans[v];
    }
    if(out>(1000000000)) cout<<"Impossible"<<"\n";
    else {
        int final=out;
        cout<<final<<"\n";
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}

 

1010

反悔贪心

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
#define int long long
int n,x,k;
int a[N];
void solve(){
    cin>>n>>x>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    int use=0;
    priority_queue<int>q;
    
    for(int i=1;i<=n;i++){
        x-=a[i];
        q.push(a[i]);
        //cout<<i<<" "<<x<<"\n";
        if(x<=0){
            while(use<k&&!q.empty()){
                x+=q.top();
                q.pop();
                use++;
                if(use==k) break;
                if(x>0) break;
            }
        }
        if(x<=0) {
            cout<<i-1<<"\n";
            return;
        }
    }
    cout<<n<<"\n";
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

 

1011

队友做的

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void Kafka()
{
    int x=read(),y=read(),d=gcd(x,y),dx=x/d,dy=y/d;
    if(dy==1) {printf("%lld %lld\n",y,dx);return;} 
    if(dy&1) {printf("%lld %lld\n",y,dx<<1LL);return;}
    else {printf("%lld %lld\n",y,dx);return;}
}
signed main()
{
    for(int T=read();T--;) Kafka();
    return 0;
}

 

1008

考虑矩阵快速幂优化

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
const int mod = 1e9+7;
typedef long long ll;
int n,m;
ll l,r;
struct Mat{
    int a[N+5][N+5];
    void init( ){
        memset(a,0,sizeof a);
    }
    void one(int n){
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++) a[i][i]=1;
    }
    Mat operator * (Mat b){
        Mat c;
        c.init();
        for(int i=1;i<=n+1;i++)
            for(int j=1;j<=n+1;j++)
                for(int k=1;k<=n+1;k++)
                    c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j]%mod)%mod;
    //    cout<<"Mat c:"<<"\n";
    //    c.print();
        return c;
    }
    void print(){
        for(int i=1;i<=n+1;i++){
            for(int j=1;j<=n+1;j++){
                cout<<a[i][j]<<" ";    
            }    
            cout<<"\n";
        }
    }
};
Mat qpow(Mat c,ll x){
    Mat ret;ret.one(n+1);
    while(x){
        if(x&1) ret=ret*c;
        c=c*c;
        x>>=1;
    //    cout<<x<<"\n";
    //    cout<<"Mat: c"<<"\n";
    //    c.print();
    }
    return ret;
}
ll work(Mat p,ll x,Mat o){
    ll t=x/n;
    ll r=x%n;
    //cout<<"t:"<<t<<"\n";
    p=qpow(p,t);
    ll ret=p.a[1][n+1];
    p=p*o;
    //cout<<"????"<<"\n";
    for(int i=1;i<=r;i++) ret=(ret+p.a[1][i])%mod;
    //cout<<x<<" ret:"<<ret<<"\n";
    return ret;
}
void solve(){
    cin>>n>>m>>l>>r;
    Mat o,o1,o2,p;
    o.init();
    o1.init();
    o2.init();
    for(int i=1;i<=n+1;i++) o2.a[i][n+1]=1;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        if(u<=n&&v<=n) o1.a[u][v]=w;
        else o2.a[u][v-n]=w;
    }
    // dp 一次
    o.one(n+1);
    for(int i=n;i>=1;i--)
        for(int j=i;j<=n;j++)
            for(int k=j;k<=n;k++)
                o.a[i][k]=(o.a[i][k]+1ll*o.a[i][j]*o1.a[j][k]%mod)%mod;
    // 行间的转移
/*    
    cout<<"Mat o:"<<"\n";
    o.print();
    cout<<"Mat o2:"<<"\n";
    o2.print();
*/
    p=o*o2;
/*
    cout<<"Mat p:"<<"\n";
    p.print();
*/
    cout<<(work(p,r,o)-work(p,l-1,o)+mod)%mod<<"\n";
}
/*
2
3 4 5 6
1 2 1
1 3 1
3 4 1
2 5 1
5 8 998244353 1000000007
1 2 114514
1 4 1919810
2 3 999999999
3 5 111111111
4 5 1000000000
1 10 123456789
5 6 987654321
3 9 888888888
*/
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
}

 

标签：杭电多校,ch,return,int,res,void,第七场,long,2024
From： https://www.cnblogs.com/liyishui2003/p/18352530

相关文章

  • 东芝新小黑移动硬盘数据被格式化如何恢复（2024年8月版）
    在数字化时代，数据已成为我们生活和工作中不可或缺的一部分。东芝新小黑移动硬盘，以其便携性和大容量，成为许多用户存储重要数据的首选。然而，当这些宝贵的数据因意外格式化而面临丢失的风险时，我们该如何应对？本文将深入探讨东芝新小黑移动硬盘数据被格式化后的恢复方法，希望帮助用户......
  • NOI 2024
    Day1T1集合(set)容易发现两个序列等价当且仅当，所有数字在序列中出现位置的集合构成集族相等。考虑哈希，对于一个集合\(S\)，令它的哈希值为\(f(S)=(\sum\limits_{x\inS}B^x)\modP\)，上述条件只需做两遍哈希即可满足。使用莫队维护所有哈希值，时间复杂度\(O(q\sqrtn\lo......
  • VS2010旗舰版VB.NET版本音频剪辑代码2024-8-10
    ImportsSystem.ComponentModelImportsSystem.IOImportsSystem.DiagnosticsImportsSystem.DrawingImportsSystem.Windows.FormsPublicClassForm1PrivateWithEventsbgWorkerAsNewBackgroundWorkerPrivateffmpegPathAsString=“C:\ffmpeg-master-lates......
  • 2024年华为OD机试真题-推荐多样性-C++-OD统一考试（C卷D卷）
    2024年OD统一考试（D卷）完整题库：华为OD机试2024年最新题库（Python、JAVA、C++合集） 题目描述：推荐多样性需要从多个列表中选择元素，一次性要返回N屏数据（窗口数量），每屏展示K个元素（窗口大小），选择策略：1.各个列表元素需要做穿插处理，即先从第一个列表中为每屏选择一个元素，再从第二个列......
  • 蓝桥杯2024年第十五届省赛A组-封印宝石
    题目描述在一次探险中，勇者小蓝发现了n颗闪烁着奇异光芒的宝石，每颗宝石都蕴含着魔法能量，分别记作a1,a2,...,an。小蓝计划用n个特制的魔法盒子来封印这些宝石，防止其魔法能量被滥用。封印宝石会消耗小蓝的体力，具体地，将第i颗宝石放入第j个盒子会消耗小蓝i−j......
  • 河南萌新联赛2024第（四）场（部分）
    I、马拉松设sum【i】为X或Y周围的且不在XY路径上的点所以这题的答案就是从sum【x】中选一个起点，sum【y】中选一个终点，答案就是sum【x】*sum【y】可以用dfs实现voiddfs(intu,intpa)//dfs是有方向的{sum[u]=1;for(autonow:v[u]){if(now......
  • 免费【2024】springboot 高校竞赛管理系统的设计与实现
    博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数......
  • 免费【2024】springboot 高校教务管理系统设计与实现
    博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数......
  • 免费【2024】springboot 高校奖助学金系统的设计与实现
    博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数......
  • 免费【2024】springboot 高校会议室预订管理系统的设计与实现
    博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99