• 思维题目专练

    大概是一些CCPC和ICPC的铜牌左右的题目和部分比较好的题，还有一些常见的trick

    题意和思路都简要写了，更多的时间要放在刷题上，还剩2-3周的时间，破釜沉舟，只愿不留遗憾。

    I. Interesting Permutation(铜，递推，构造)
    题意：要构造排列p，给定h数组，hi是排列p的前缀i的最大值和最小值的差，给定h数组请你求出p的构造方式有多少种。

    思路：递推，当h更新说明最大值或者最小值更新，方案数乘二同时更新最大值最小值又多产生了max-min个中间的数，不变说明从中间的数中选了一个放进去。

    #include
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e5+100;
int a[N];
map<int,int>mp;
const int mod = 1e9+7;
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        bool falg=true;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]>n-1)
                falg=false;
        }
        if(a[1]!=0||a[n]!=n-1)
            falg=false;
        int sum=0;
        int ans=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]>a[i-1])
            {
                ans=ans*2%mod;
                sum+=a[i]-a[i-1]-1;
            }
            if(a[i]==a[i-1])
            {
                ans=ans*sum%mod;
                sum--;
            }
            if(a[i]<a[i-1])
                falg=false;
        }
        if(falg)
        cout<<ans<<endl;
        else
        cout<<0<<endl;
    }
   return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    I. Power and Zero（铜，二进制，贪心）
    题意：给定一组数a，你每次可以安排一个数组b，b的元素是a数组中的并且可以重复选择同一个元素，让b的每个位置都减去2i-1，请问最少多少次操作可以让数组变为0。

    思路：我们从低位二进制位开始，每次尽可能向高位进发，也就是取最长的一段连续二进制位让每一位都减少1，如果遍历到的这个二进制位没有了，那么向高位去借。

    #include
#define int long long
#define endl '\n'

using namespace std;
const int N=1e5+5;
int n,a[N],sum;
int bits[50];
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--)
    {
        int n,sum=0;
        memset(bits,0,sizeof(bits));
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            int temp=a[i];
            int cnt=0;
            while(temp)
            {
                if(temp&1)
                {
                    bits[cnt]++;
                    sum++;
                }
                cnt++;
                temp>>=1;
            }
        }
        int ans=0;
        while(sum>0)
        {
            ans++;
            for(int i=0;i<=30;i++)
            {
                if(bits[i]>0)
                {
                    bits[i]--;
                    sum--;
                }
                else
                {
                    for(int j=i;j<=30;j++)
                    {
                        if(bits[j])
                        {
                            for(int k=j;k>i;k--)
                            {
                                bits[k]--;
                                 bits[k-1]+=2;
                                sum++;
                            }
                            bits[i]--;
                            sum--;
                            break;
                        }
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    E - Power and Modulo （签，数学）
    题意：给定一个数组，请你找出一个唯一确定的数m，使得数组满足等式 a[i]=2i-1%m

    思路：找到第一个不等于2i-1的a[i]，不难看出m是介于(2i-2，2i-1]之间的所以不存在倍数关系，可以唯一确定一个数m=2i-1-a[i]，然后对于整个数组验证一遍即可。

    #include
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e6+100;
int a[N];
int two[N];
signed main()
{
    //cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        int pos=0;
        bool falg=true;
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=(1ll<<(i-1)))
            {
                if(a[i]>(1ll<<(i-1)))
                {
                    falg=false;
                }
                pos=i;
                break;
            }
        }
        if(!pos)
            falg=false;
        int mod;
        if(falg)
        {
            mod=(1ll<<(pos-1))-a[pos];
            two[0]=1ll%mod;
            for(int i=1;i<=n;i++)
            {
                two[i]=two[i-1]*2ll%mod;
            }
            for(int i=1;i<=n;i++)
            {
                //cout<
                if(two[i-1]!=a[i])
                {
                    falg=false;
                }
            }
        }
        if(falg)
            cout<<mod;
        else
            cout<<-1;
        if(t!=1)
            cout<<endl;
    }
   return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    E. Prof. Pang and Poker（银，博弈，分类讨论）

    在这里插入图片描述

    思路：分类讨论，具体看代码就可以了。

    #include 
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
using namespace std;
const int N = 1e5 + 55;
int n, m;
int a[N], b[N];

int getcard() {
    static char s[5];
    cin >> s;
    if(s[0] == 'T') return 10;
    else if(s[0] == 'J') return 11;
    else if(s[0] == 'Q') return 12;
    else if(s[0] == 'K') return 13;
    else if(s[0] == 'A') return 14;
    else return s[0] - '0';
}

signed main(){
    //freopen("E.in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int Task; cin >> Task;
    while(Task--) {
        cin >> n >> m;
        int A0_max = -1, A1_max = -1, B0_max = -1, B1_max = -1;
        int A0 = 0, B0 = 0, A1 = 0, B1 = 0;
        int X;
        rep(i, 1, n) a[i] = getcard();
        rep(i, 1, m) b[i] = getcard();
        X = getcard();
        rep(i, 1, n) {
            int y = a[i];
            if(y < X) ++A0, A0_max = max(A0_max, y);
            else ++A1, A1_max = max(A1_max, y);
        }
        rep(i, 1, m) {
            int y = b[i];
            if(y < X) ++B0, B0_max = max(B0_max, y);
            else ++B1, B1_max = max(B1_max, y);
        }
        int ok = 0;
        if(A0 == 1 && A1 == 0) ok = 0;
        else if(A0 == 0) ok = 0;
        else if(A0 >= 1) {
            if(B0 >= 2) ok = 1;
            else if(B0 == 0) ok = 0;
            else if(B0 == 1) {
                if(A0_max < B0_max) ok = 0;
                else {
                    if(B1 == 0) ok = 1;
                    else if(B1 > 0 && A1 == 0) ok = 0;
                    else if(A1_max > B1_max) {
                        if(A0 == 1 || A0 + A1 <= 3) ok = 0;
                        else ok = 1;
                    }
                    else ok = 0;
                }
            }
        }
        ok ? puts("Pang") : puts("Shou");
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    I. Dragon Bloodline（银，二分答案）
    题意：现在有龙要下蛋，下一个蛋需要n种材料每个材料要a[i]个，有k个等级的工具龙，每个等级的工具龙有b[i]条，等级为i的工具龙可以收集2i-1个材料，现在想要下蛋数量最大化，请你求出最多能下多少蛋。

    思路：二分答案，，也没啥好说的，注意控制上界别超过longlong，注意控制下界到0

    贪心策略就是先用最强的工具龙，然后在不超过每个材料要求的情况下去收集材料，多余的工具龙优先去收集目前剩余需求量最大的材料。

    #include 

using namespace std;
#define int long long
#define endl '\n'
const int N = 1e6+100;
int a[N],b[N];
int ta[N],tb[N];
int n,k;
bool cmp(const int a,const int b)
{
    return a>b;
}
bool check(int x)
{
    for(int i=1;i<=n;i++)
        ta[i]=a[i]*x;
    for(int i=1;i<=k;i++)
        tb[i]=b[i];
    for(int i=k;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
        {
            if(!tb[i])
                break;
            int num=min(tb[i],ta[j]/(1<<(i-1ll)));
            ta[j]-=num*(1ll<<(i-1ll));
            tb[i]-=num;
        }
        if(tb[i])
        {
            tb[i]=min(tb[i],n);
            sort(ta+1,ta+n+1,cmp);
            //nth_element(ta+1,ta+tb[i],ta+n+1,greater());
            for(int j=1;j<=tb[i];j++)
            {
                ta[j]=0;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(ta[i])
            return false;
    }
    return true;
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int suma=0,sumb=0;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            suma+=a[i];
        }
        for(int i=1;i<=k;i++)
        {
            cin>>b[i];
            sumb+=(b[i]*(1<<(i-1)));
        }
        int l=0,r=sumb/suma,ans=0;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid))
                l=mid+1,ans=mid;
            else
                r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    E - Crystal Switches（铜，BFS最短路，分层图）
    题意：一张图上n个点m条边，每条边权值为1可以走，为0不能走，有k个节点上有开关，启用开关之后全部的边都节点权值-1
    请你求出节点1到n的最短步数。

    思路：BFS最短路，所有含有开关的点视为有一个派生节点，记录一下当前开关使用次数，每次走边的时候判断通透性即可。

    #include 
using namespace std;
#define endl '\n'
#define lowbit(x) ((x)&(-x))
#define int long long
//#define ll long long
#define pause system("pause")
const int mod=1e9+7;
const int inf=1e18;
const int N = 1e6+100;
const double eps=1e-10;

int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int sgn(double x)
{
    if(fabs(x)<eps) return 0;
    else if(x<0) return -1;
    else return 1;
}
int getinv(int a){return qpow(a,mod-2LL);}
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int head[N],cnt;
struct Edge
{
    int next,to,w;
}e[N];
void addedge(int from,int to,int w)
{
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].w=w;
    head[from]=cnt;
}
int n,m,k,s[N],vis[N][2];
struct node
{
    int id,dis,fg;
};
void bfs()
{
    queue<node>q;
    q.push(node{1,0,0);
    if(s[1])
    q.push(node{1,0,1});
    int ans=-1;
    while(!q.empty())
    {
        int u=q.front().id,dis=q.front().dis,fg=q.front().fg;q.pop();
        if(u==n){ans=dis;break;}
        if(vis[u][fg]) continue;
        vis[u][fg]=1;
        for(int i=head[u];i;i=e[i].next)
        {
            int j=e[i].to;
            if((fg^e[i].w)==0) continue;
            q.push(node{j,dis+1,fg});
            if(s[j]) q.push(node{j,dis+1,fg^1});
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) vis[i][0]=vis[i][1]=s[i]=0;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
        addedge(v,u,w);
    }
    for(int i=1;i<=k;i++)
    {
        int x;cin>>x;s[x]=1;
    }
    bfs();
    pause;
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93

    C - Ladder Takahashi（签，节点离散化+DFS）
    题意：n个梯子，每个梯子链接的楼层是a和b，现在你从第1层开始，请问最高能爬到多高。

    思路：由于楼层最大取值1e9，所以一开始考虑离散化并查集，写挂了（）

    然后想着直接建图用DFS全部跑一遍就好了，然后就过了。

    #include 
using namespace std;
#define int long long
#define endl '\n'
const int N = 2e6+100;
int num[N];
map<int,int>mp;
struct node
{
    int nex,to;
}edge[N<<1];
int head[N],tot;
void add(int from,int to)
{
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
}
int maxx=1;
int vis[N];
void DFS(int now,int fa)
{
    if(vis[now])
        return ;
    maxx=max(num[now],maxx);
    vis[now]=1;
    for(int i=head[now];i;i=edge[i].nex)
    {
        int to=edge[i].to;
        if(to==fa||vis[to])
            continue;
        DFS(to,now);
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    int cnt=1;
    mp[1]=1;
    num[1]=1;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        if(!mp[a])
        {
            mp[a]=++cnt;
            num[cnt]=a;
        }
        if(!mp[b])
        {
            mp[b]=++cnt;
            num[cnt]=b;
        }
        //cout<
        add(mp[a],mp[b]);
        add(mp[b],mp[a]);
    }
    DFS(1,0);
    cout<<maxx;
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65

    D - Takahashi’s Solitaire（签，循环数组）
    题意：有n个小于m大于等于0的数，第一次打出这些数中任意一个，设截止当前时刻最后一次打出的数是x，随后每次可以打出值为x或者（x+1）%m的数。

    请问什么策略下，打出数之后，剩下的数的和最小

    思路：显然，构成了一个环，我们的任务就是把和最大的一段弧给从整个环里减去。

    #include 
using namespace std;
#define int long long
#define endl '\n'
const int N = 2e6+100;
int num[N];
map<int,int>mp;
struct node
{
    int nex,to;
}edge[N<<1];
int head[N],tot;
void add(int from,int to)
{
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
}
int maxx=1;
int vis[N];
void DFS(int now,int fa)
{
    if(vis[now])
        return ;
    maxx=max(num[now],maxx);
    vis[now]=1;
    for(int i=head[now];i;i=edge[i].nex)
    {
        int to=edge[i].to;
        if(to==fa||vis[to])
            continue;
        DFS(to,now);
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    int cnt=1;
    mp[1]=1;
    num[1]=1;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        if(!mp[a])
        {
            mp[a]=++cnt;
            num[cnt]=a;
        }
        if(!mp[b])
        {
            mp[b]=++cnt;
            num[cnt]=b;
        }
        //cout<
        add(mp[a],mp[b]);
        add(mp[b],mp[a]);
    }
    DFS(1,0);
    cout<<maxx;
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
  • 相关阅读:
    requests爬虫详解
    Docker ------compose概述与简单编排部署
    C 标准库 - ＜time.h＞和＜float.h＞详解
    含文档+PPT+源码等]精品微信小程序ssm驾校教培服务系统小程序+后台管理系统|前后分离VUE[包运行成功]微信小程序项目源码Java毕业设计
    Android事件分发机制
    入门力扣自学笔记131 C++ （题目编号655）
    Java27岁了——我与Java初识
    【算法03】对数器
    第三届VECCTF-2023 Web方向部分wp
    cario库——C++画图
  • 原文地址：https://blog.csdn.net/qq_35866893/article/details/127835936