Dewy-Wiki

杭电杯第一场

ClearDewy大约 6 分钟

杭电杯第一场

个人题解，欢迎指正

P1002

题目大意：

给定网格大小，起点和终点，求到达终点的最小摧毁墙的数量

思路：

由于数据范围较小，我们可以枚举剩余的墙然后再跑DFSDFS或BFSBFS，时间复杂度O(n∗m∗2k)O(n*m*2^k)

墙在网格线上，走的是格子，我们可以把网格大小扩大一倍，使得路径和墙都在网格上

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x)   ((x)&(-x))
#define fi first
#define se second
#define pb push_back
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    x *= f;
}
int main()
{
    int T;
    read(T);
    while (T--)
    {
        int n,m,k;
        read(n),read(m),read(k);
        int xs,ys,xt,yt;
        n = n * 2,m = m * 2;//扩大两倍
        read(xs),read(ys),read(xt),read(yt);
        xs = xs * 2 + 1,ys = ys * 2 + 1,xt = xt * 2 + 1,yt = yt * 2 + 1;//扩大两倍(原点)
        vector<pair<pii,pii>> query(k + 1); 
        for(int i = 1;i <= k;i++)
        {
            int xl,yl,xr,yr;
            read(xl),read(yl),read(xr),read(yr);
            xl = xl * 2,yl = yl * 2,xr = xr * 2,yr = yr * 2;//扩大两倍
            query[i] = {{xl,yl},{xr,yr}};//记录墙
        }

        bool st[17] = {0};
        int ans = k;

        auto bfs = [&](int cnt) -> void
        {
            bool ok = false;
            bool S[50][50] = {0};
            for(int i = 1;i <= k;i++)//预处理
            {
                if(st[i])   continue;
                if(query[i].fi.fi == query[i].se.fi)//横轴相等
                {
                    int mi = min(query[i].fi.se,query[i].se.se),mx = max(query[i].fi.se,query[i].se.se);
                    for(int k = mi;k <= mx;k++) S[query[i].fi.fi][k] = true;
                }
                else//纵轴相等
                {
                    int y = query[i].fi.se;
                    int mi = min(query[i].fi.fi,query[i].se.fi),mx = max(query[i].fi.fi,query[i].se.fi);
                    for(int k = mi;k <= mx;k++) S[k][y] = true;
                }
            }

            queue<pii> q;
            q.push({xs,ys});
            bool stt[50][50] = {0};

            while (q.size())
            {
                auto t = q.front();

                q.pop();
                if(stt[t.fi][t.se])   continue;
                stt[t.fi][t.se] = true;
                
                int dx[] = {-2,0,2,0},dy[] = {0,2,0,-2};//左，上，右，下
        
                for(int i = 0;i < 4;i++)
                {
                    int nx = t.first + dx[i],ny = t.second + dy[i];
                    if(nx >= 0 && nx < n && ny >= 0 && ny < m)
                    {
                        if(!i || i == 2)
                        {
                            if(!S[t.fi + dx[i] / 2][ny] && !stt[nx][ny]) q.push({nx,ny});
                        }
                        else
                        {
                            if(!S[nx][t.se + dy[i] / 2] && !stt[nx][ny]) q.push({nx,ny});
                        }
                    }
                }
            }
            if(stt[xt][yt])   ok = true;
            else    ok = false;

            if(ok)  ans = min(ans,cnt);
        };

        for(int i = 0;i < 1 << k;i++)
        {
            memset(st,0,sizeof(st));
            int cnt = 0;
            for(int j = 0;j < k;j++)
            {
                if(i >> j & 1)
                {
                    st[j + 1] = true;
                    cnt++;
                }
            }
            bfs(cnt);
        }
        printf("%d\n",ans);
    }
    
    return 0;
}

P1009

题目大意：

给定nn个点，判断这nn个点是否能构成一个“米”字型

思路：

首先确定一个点为中心，遍历其他点，找到一个不在此“米”字上的一个点，然后就可以根据这两个点确定“米”字型，情况数A42=12A^2_4=12种，然后分别遍历判断是否有其他点不在“米”字上

tip：只用求出66种情况的坐标，因为只用把两个点交换就可以得到另外66个点的坐标

Code:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}
const double INF=0x3f3f3f3f;
int n;

double asd(double x){
    return x<0?-x:x;
}

const double dsa=1e-9;

bool che(pair<double,double>&a,pair<double,double>&b){
    if(asd(a.first-b.first)<dsa)return 1;
    if(asd(a.second-b.second)<dsa)return 1;
    if(asd(asd(a.first-b.first)-asd(a.second-b.second))<dsa)return 1;
    return 0;
}
vector<pair<double,double>>a(n+1);

bool judge(pair<double,double>ha){
    for (int i = 1; i <= n; i++)
    {
        if(!che(ha,a[i])){
            return 0;
        }
    }
    return 1;
}

void Qingtuan(){
    n=read();
    a.resize(n+1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf%lf",&a[i].first,&a[i].second);
    }
    bool ju=1;
    pair<double,double>h;
    for (int i = 2; i <= n; i++)
    {
        if(!che(a[1],a[i])){        //找出一个不在以a[1]为中心的“米”字的点
            ju=0;
            h=a[i];break;
        }
    }
    if(ju){
        puts("YES");return;
    }
    pair<double,double>p,q,ha;
    p=a[1];q=h;
	
    //1
    if(judge({q.first,p.second})){
        puts("YES");return;
    }
    swap(p,q);
    if(judge({q.first,p.second})){
        puts("YES");return;
    }
    //2
    if(judge({q.first-q.second+p.second,p.second})){
        puts("YES");return;
    }
    swap(p,q);
    if(judge({q.first-q.second+p.second,p.second})){
        puts("YES");return;
    }

    //3
    if(judge({q.first+q.second-p.second,p.second})){
        puts("YES");return;
    }
    swap(p,q);
    if(judge({q.first+q.second-p.second,p.second})){
        puts("YES");return;
    }

    //4
    if(judge({p.first,q.first-p.first+q.second})){
        puts("YES");return;
    }
    swap(p,q);
    if(judge({p.first,q.first-p.first+q.second})){
        puts("YES");return;
    }

    //5

    if(judge({p.first,q.second-q.first+p.first})){
        puts("YES");return;
    }
    swap(p,q);
    if(judge({p.first,q.second-q.first+p.first})){
        puts("YES");return;
    }

    //6
    if(judge({(p.first+q.first+q.second-p.second)/2,(p.second+q.first+q.second-p.first)/2})){
        puts("YES");return;
    }
    swap(p,q);
    if(judge({(p.first+q.first+q.second-p.second)/2,(p.second+q.first+q.second-p.first)/2})){
        puts("YES");return;
    }

    puts("NO");
}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    Qingtuan();
    WA
}

P1011

题目大意：

在[0,1][0,1]之间随机生成nn个数，然后分别有一半的可能去掉mm个最大或最小的数，求最后剩余数字和的期望

思路：

因为数字大小概率相等，所以生成数字的均值为0.50.5，去掉mm个最大最小的数均值也为0.50.5,所以最后结果为n−m2\frac{n-m}{2},因为是对109+710^9+7取模，只需要处理一下22的逆元即可

Code:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}

ll mod=1e9+7;

inline ll fp(ll x, ll y) {
    ll base = 1;
    while (y)
    {
        if (y&1)
            base =base*x%mod;
        x=x*x%mod;y >>= 1;
    }
    return base;
}

ll n,m;
ll inv2;

void Qingtuan(){
    n=read();m=read();
    writ((n-m)*inv2%mod);ptn;
}

int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);
    inv2=fp(2,mod-2);
    int T=read();while (T--)
    Qingtuan();
    WA
}

P1012

题目大意：

AliceAlice可以把一堆数分成两堆，BobBob可以选择一堆并擦去，剩余一堆数字减半，当黑板上出现00则AliceAlice胜出，黑板上数字都被擦完了则BobBob胜出

思路：

首先分析两种最简单的情况

  • 黑板上有00或只有一个11时，AliceAlice必胜

  • 黑板上有两个11时，BobBob必胜

我们尝试将数字全部转化为11的个数来进行判断，举个例子：

  • 黑板上为1,2,2{1,2,2}时候，分为1{1}和2,2{2,2},此时BobBob必胜

  • 假如只有22,当22的个数为44及以上时，BobBob必胜

  • 假如只有33,当22的个数为88及以上时，BobBob必胜

​ ……\dots\dots

我们发现，当一个数为nn的时候，对n−1n-1的贡献为 个数2\frac{个数}{2},对n−2n-2的贡献为 个数4\frac{个数}{4},此时就可以把每个数转化为11的个数来进行判断

可以将贡献理解为相当于，比如两个22就相当于一个11

Code:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}

ll n;


void Qingtuan(){
    n=read();
    vector<ll>a(n+1);
    for (int i = 0; i <= n; i++)
    {
        a[i]=read();
    }
    if(a[0]){
        puts("Alice");return;
    }
    for (int i = n; i >1; i--)
    {
        a[i-1]+=a[i]>>1;
    }
    if(a[1]>=2)
        puts("Alice");
    else
        puts("Bob");


}


int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    Qingtuan();
    WA
}
版权 @2022 清漙
Copyright © 2024 ClearDewy