首页 > 其他分享 >思维题

思维题

时间:2023-06-29 21:24:18浏览次数:34  
标签:思维 ch int void long write define

CF690A2

题面

考虑没有钱的情况,可以发现只有 \(n=2^k\) 情况可行。为了最少,显然每个人钱数为 \(0/1\),当有 \(m\) 钱,可以将这 \(m\) 钱分给最后 \(m\) 个人,这样一定会有 \(m\) 人投支持票,第 \(2\sim m+1\) 个人显然可以复制这个操作,所以会投反对票,这样就又回到了没有钱的情况。所以得出结论,找出 \(2^k+2m=n\) 的最小 \(m\) 即可。

CF690A3

题面

直接猜自己的数字是不可猜的,转换一下思路,猜所有人的数字之和在模 \(n\) 意义下的和,令第 \(r\) 个僵尸猜的和模 \(n\) 为 \(r-1\) 即可。

[AGC016E] Poor Turkey

题面

做题关键:“留着你是为了把你炖了”。

因为题目说的是存在可能性,那么本质来说就是问我们能否构造一种不死的方案。这说明每次 \(i/j\) 要死的时候,都会有鸡帮它们挡刀。考虑将按时间从大往小考虑,令 \(f_{i,x}\) 表示如果 \(i\) 要活下来,\(x\) 是否要在某个时间前活下来。用 bitset 维护,最后判断如果 \(i,j\) 均要活下来是否会有冲突即可。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=410,M=1e5+10;
int n,m,a[M],b[M],flag[N];
bitset<N>f[N];
void solve(){
    read(n),read(m);
    for(int i=1;i<=m;i++){
        read(a[i]),read(b[i]);
    }
    for(int i=1;i<=n;i++){
        f[i][i]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j;j--){
            if(f[i][a[j]]&&f[i][b[j]]){
                flag[i]=1;
            }
            if(f[i][a[j]]){
                f[i][b[j]]=1;
            }
            if(f[i][b[j]]){
                f[i][a[j]]=1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(!flag[i]&&!flag[j]&&((f[i]&f[j]).none())){
                ans++;
            }
        }
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

CF618F

题面

高考引流题,并没有想象中的难。

令 \(x=suma-sumb\),一个策略,在 \(x<n\) 时,选择 \(a\) 中的数,反之选择 \(b\) 中的数。可以发现无论什么时刻,\(x\in[0,2n)\),但总共有 \(2n+1\) 个时刻,因为开始选数前也是一个时刻,根据鸽巢原理,必然会有两个时刻 \(x\) 相同,即没有无解情况。这两个相同时刻之间选择的数就是我们要的答案。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e6+10;
int n,a[N],b[N],flag[N];
pii p[N];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    for(int i=1;i<=n;i++){
        read(b[i]);
    }
    int posa=0,posb=0,delta=0;
    flag[0]=1;
    for(int i=1;i<=n*2;i++){
        if(delta<n){
            delta+=a[++posa];
        }
        else{
            delta-=b[++posb];
        }
        if(flag[delta]){
            write_endl(posa-p[delta].first);
            for(int i=p[delta].first+1;i<=posa;i++){
                write_space(i);
            }
            putchar('\n');
            write_endl(posb-p[delta].second);
            for(int i=p[delta].second+1;i<=posb;i++){
                write_space(i);
            }
            return;
        }
        flag[delta]=1;
        p[delta]=mp(posa,posb);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

CF505E

题面

看到最大值最小,想到二分答案。证明单调性,如果少砍一下,最大值必然大于等于最优的最大值,证毕。

因为正着操作不方便处理,考虑将操作反过来。操作更改为每一轮后 \(h_i\) 变为 \(h_i-a_i\),操作前 \(h_i\ge a_i\);进行 \(k\) 次操作,每次选择一个 \(h_i\) 变为 \(h_i+p\);要求最终的 \(h_i\) 不小于给定的 \(n\) 个数。因为如果大于给出的 \(a_i\)

贪心考虑,每次选择最容易导致 \(h_i-a_i<0\) 的 \(i\) 加上 \(p\),如果不能使得没有 \(h_i-a_i<0\) 则显然不合法。到最后,将剩余操作次数分配一下,判断能否使所以 \(h_i\) 大于等于 \(a_i\)。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e5+10;
int n,m,k,p,a[N],h[N],num[N],ans,l,r=0x3f3f3f3f;
bool chk(int val){
    priority_queue<pii>q;
    for(int i=1;i<=n;i++){
        if(h[i]+m*a[i]<=val){
            continue;
        }
        q.push(mp(-(val/a[i]),i));
        num[i]=0;
    }
    int cnt=0;
    for(int i=1;i<=m;i++){
        if(q.empty()){
            break;
        }
        for(int j=1;j<=k;j++){
            if(q.empty()){
                break;
            }
            int x=-q.top().first,y=q.top().second;
            q.pop();
            if(x<i){
                return 0;
            }
            num[y]++;
            int w=(val+num[y]*p)/a[y];
            if(w<m){
                q.push(mp(-w,y));
            }
            cnt++;
        }
    }
    for(int i=1;i<=n;i++){
        int w=val+num[i]*p-m*a[i];
        if(h[i]<=w){
            continue;
        }
        int sum=(h[i]-w-1)/p+1;
        cnt+=sum;
        if(cnt>m*k){
            return 0;
        }
    }
    return 1;
}
void solve(){
    read(n),read(m),read(k),read(p);
    for(int i=1;i<=n;i++){
        read(h[i]),read(a[i]);
        l=max(l,a[i]);
        r=max(r,a[i]*m+h[i]);
    }
    while(l<=r){
        int mid=(l+r)>>1;
        if(chk(mid)){
            r=mid-1;
            ans=mid;
        }
        else{
            l=mid+1;
        }
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

CF911F

题面

一个结论:和一个点距离最远的点一定为直径两端点之一。对于直径上的点显然,对于不在直径上的点 \(x\),令 \(y\) 为直径上距离 \(x\) 最近的点,因为距离 \(y\) 最远的点为直径的端点,加上一个 \(dis_{x,y}\),距离 \(x\) 最近的点仍是直径的一个端点。

所以找到直径,先处理不在直径上的点,再处理直径上的点即可。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10;
int n,rt,mx,dep[N];
vector<int>e[N];
void dfs(int u,int fa){
    if(dep[u]>mx){
        rt=u;
        mx=dep[u];
    }
    for(auto v:e[u]){
        if(v==fa){
            continue;
        }
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
}
vector<int>line,stk;
int vis[N],dis[N],deg[N];
void find(int u,int fa,int to){
    stk.pb(u);
    if(u==to){
        line=stk;
    }
    for(auto v:e[u]){
        if(v==fa){
            continue;
        }
        find(v,u,to);
    }
    stk.pop_back();
}
void count(int u,int d,int fa){
    if(!vis[u]){
        vis[u]=fa;
        dis[u]=d;
    }
    for(auto v:e[u]){
        if(vis[v]){
            continue;
        }
        count(v,d+1,fa);
    }
}
void solve(){
    read(n);
    for(int i=1;i<n;i++){
        int u,v;
        read(u),read(v);
        e[u].pb(v);
        e[v].pb(u);
    }
    dfs(1,0);
    int rtt=rt;
    mx=0;
    dfs(rt,0);
    find(rt,0,rtt);
    for(int i=0;i<line.size();i++){
        int x=line[i];
        vis[x]=x;
        dis[x]=i;
    }
    for(auto x:line){
        count(x,0,x);
    }
    vector<tuple<int,int,int>>ans;
    queue<int>q;
    ll ans_num=0;
    for(int i=1;i<=n;i++){
        deg[i]=e[i].size();
        if(vis[i]==i){
            continue;
        }
        if(deg[i]==1){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(vis[u]==u){
            continue;
        }
        int top=vis[u];
        if(dis[top]>=line.size()-dis[top]-1){
            ans.pb(make_tuple(u,rt,u));
            ans_num+=dis[u]+dis[top];
        }
        else{
            ans.pb(make_tuple(u,rtt,u));
            ans_num+=dis[u]+line.size()-dis[top]-1;
        }
        for(auto v:e[u]){
            deg[v]--;
            if(deg[v]==1){
                q.push(v);
            }
        }
    }
    while(line.size()>1){
        int u=line.back();
        line.pop_back();
        ans.pb(make_tuple(u,rt,u));
        ans_num+=dis[u];
    }
    write_endl(ans_num);
    for(auto x:ans){
        write_space(get<0>(x)),write_space(get<1>(x)),write_endl(get<2>(x));
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

标签:思维,ch,int,void,long,write,define
From: https://www.cnblogs.com/luoshen0/p/17459074.html

相关文章

  • 思维决定格局,分享40个经典的思维模型~
    学习力1学习金字塔主动式学习,才是有效的学习!2费曼技巧(费曼学习法)想学会一个知识,不如尝试把它教给别人~3刻意练习专注、重复、持续反馈。4RIA阅读法用自己的语言重述知识,并结合自己的相关经验,思考今后如何运用。5二八定律要用80%的时间做好那20%最重要的事!思......
  • 产品读书《互联网思维独孤九剑:移动互联网时代的思维革命》
    互联网思维独孤九剑PPT1 互联网思维独孤九剑PPT2互联网思维独孤九剑PPT3  互联网思维的定义在(移动)互联网、大数据、、云计算等科技不断发展的背景下,对市场、对用户、对产品、对企业价值链乃至对这商业生态的进行重新审视的思考方式。  1.用户思维指对经营理念和消费者的理解......
  • 院士口中的“现代人知识结构”,学者推崇的“效率公民必备”,统计思维到底有什么了不起?..
    0要问现代人最难逃离哪种数学,概率与统计必须拥有姓名。“学者不能离开统计而究学,实业家不能离开统计而执业,政治家不能离开统计而施政。”统计应用之广,横跨文理,纵贯研究与实践。人们不断谈论“根据数据进行决策”“通过数据阐明情况”“观察数据得出结论”……其中的“数据”常常就......
  • 「思维拓展/个人提升」简说
    这里想要记录的是除了专业领域知识之外的见识,艺术、文学、商业、经济、生物、创业、IT、物理、哲学、心理学等等领域,千万不要把自己局限在一个小的圈子里。虽说术业有专攻,但也不是让你将自己限死在一个领域,事实上,行业之间,知识之间是互通的,生物上面的一个创新可能是你的一个创业idea......
  • 外贸业务员应该具备哪些思维方式,才能大单不断?
    成为一个外贸业务员也许很容易,但成为一名优秀的外贸业务员绝非简单事。只注重专业技能的“硬件”是远远不够的,需“软硬兼施”。所以,今天贸小七从外贸业务员的“软件”方面之一——思维方式,聊聊怎样成为一名优秀的外贸业务员。外贸业务员思维一:“售出产品的第一步是销出自己”外贸业......
  • 活动回顾 | 汇聚行业技术大咖,共享思维碰撞时刻,2023 Meet TVM · 北京站圆满落幕
    内容一览:「2023MeetTVM·北京站」于6月17日在中关村车库咖啡顺利举办,现场吸引了来自企业和高校的150余名参与者,大家进行了充分热烈的讨论。关键词:机器学习编译2023MeetTVM本文首发自HyperAI超神经微信公众平台~6月17日,由MLC.AI及HyperAI超神经主办、Op......
  • Java编程专题思维导图
    ......
  • Java基础知识思维导图
    ......
  • Servlet&JSP思维导图
    ......
  • 前端学习笔记_思维导图和资源链接
    17素材资源jQueryapi中文文档脑图-前端总结脑图-jquery总结脑图-js正则总结后台主题框架echartsjQuery插件adminlte......