首页 > 其他分享 >2022杭电多校1

2022杭电多校1

时间：2022-09-28 11:33:10浏览次数：89  
标签：杭电多校 const int cin long 2022 include define

1002 Dragon slayer

题目大意：

给出一张的网格地图，给出起点和终点(均为方格的正中心)，其中地图中有面墙阻隔了道路，每面墙都在网格线上并保证墙横平竖直，以线段端点的形式给，

问从起点到终点最少要破坏多少面墙

分析：

发现数据都是<=15 所以直接枚举破坏墙的方案

对每一种二进制方案bfs判断是否可以到达终点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1005;

int n,m,k;

int vis[maxn];

int st[maxn][maxn],pos[maxn][maxn];

int dx[5]={0,1,0,-1};
int dy[5]={1,0,-1,0};

struct node {
    int a,b,c,d;
}que[maxn];


int main(){

    IOS

    int T;
    cin>>T;
    while(T--){
        cin>>n>>m>>k;
        int ans=k;
        for(int i=0;i<=100;i++){
            for(int j=0;j<=100;j++){
                pos[i][j]=0;
            }
        }
        int cnt=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                pos[i][j]=++cnt;
            }
        }
        int u,v,s,t;
        cin>>u>>v>>s>>t;
        for(int j=0;j<k;j++){
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            que[j]={x1,y1,x2,y2};
        }
        for(int ji=0;ji<(1<<k);ji++){
            for(int i=0;i<=n*m+5;i++)vis[i]=0;
            int res=k;
            for(int i=0;i<k;i++){
                if(ji>>i&1){
                    int x1=que[i].a,y1=que[i].b,x2=que[i].c,y2=que[i].d;
                    if(x1>x2)swap(x1,x2);
                    if(y1>y2)swap(y1,y2);
                    if(x1==x2){
                        for(int j=y1;j<y2;j++){
                            st[pos[x1-1][j]][pos[x2][j]]=1;
                            st[pos[x2][j]][pos[x1-1][j]]=1;
                        }
                    }else {
                        for(int j=x1;j<x2;j++){
                            st[pos[j][y1-1]][pos[j][y1]]=1;
                            st[pos[j][y1]][pos[j][y1-1]]=1;
                        }
                    }
                    res--;
                }
            }
            queue<pii>q;
            q.push({u,v});
            while(q.size()){
                pii top=q.front();
                q.pop();
                vis[pos[top.first][top.second]]=1;
                for(int j=0;j<4;j++){
                    int x=top.first+dx[j],y=top.second+dy[j];
                    if(x<0||x>=n||y<0||y>=m)continue;
                    if(vis[pos[x][y]])continue;
                    if(st[pos[top.first][top.second]][pos[x][y]])continue;
                    q.push({x,y});
					vis[pos[x][y]]=1;
                }
            }
            for(int i=0;i<k;i++){
                if(ji>>i&1){
                    int x1=que[i].a,y1=que[i].b,x2=que[i].c,y2=que[i].d;
                    if(x1>x2)swap(x1,x2);
                    if(y1>y2)swap(y1,y2);
                    if(x1==x2){
                        for(int j=y1;j<y2;j++){
                            st[pos[x1-1][j]][pos[x2][j]]=0;
                            st[pos[x2][j]][pos[x1-1][j]]=0;
                        }
                    }else {
                        for(int j=x1;j<x2;j++){
                            st[pos[j][y1-1]][pos[j][y1]]=0;
                            st[pos[j][y1]][pos[j][y1-1]]=0;
                        }
                    }
                }
            }
            if(vis[pos[s][t]])ans=min(ans,res);
        }
        cout<<ans<<endl;
    }
}

1011 Random


签到题没啥说的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define endl '\n'

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;
const int mod=1e9+7;

ll ksm(ll a,ll b){
    ll ans=1,base=a%mod;
    while(b){
        if(b&1)
            ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans;
}

ll inv(ll x){
    return ksm(x,mod-2)%mod;
}

int main(){

    IOS
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        cout<<(n-m)*inv(2)%mod<<endl;
    }
}

L Alice And Bob

题意：

有n个数，每次Alice可以把这些数分成两个集合，Bob可以删除掉任意一个集合里的所有元素，然后另一个集合内所有元素-1，如果集合中出现了0，那么

Alice获胜，如果集合内没有元素了Bob获胜。

分析：

这个题还是挺有难度的

首先想Ailce必胜 如果此时有至少两个1 我们把这两个1分别放一堆 这样是必胜

继续想后续状态 也就是有四个2 八个3 ....这样都是必胜

但是除了这样就没有别的必胜的状态了嘛？ 肯定不是

比如 2 2 2 3 3

第一堆 2 2

第二堆2 3 3

Bob只有将第一堆删去 但是这样第二堆变成1 2 2 了

我们再分

第一堆 1

第二堆 2 2

同样也是必胜状态

怎么总结这个规律呢？

两个相同的数 等价于一个减一的数

从大到小依次处理就好

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define endl '\n'

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;
const int mod=1e9+7;

int n,a[maxn];
int main(){

    IOS
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        int flg=0,now=1;
        for(int i=0;i<=n;i++)cin>>a[i];
        for(int i=n;i>=1;i--)a[i-1]+=a[i]/2;

        if(a[0])cout<<"Alice"<<endl;
        else cout<<"Bob"<<endl;
    }
}

1003 Backpack

题目大意：

01背包求恰好装满时的价值最大异或和

分析：

让我想到了这个题目

https://www.acwing.com/problem/content/1456/

这个题目就直接转移就好

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7, N = 1 << 13;
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int cnt = 0;
    vector<int> prime(N + 1);
    vector<bool> st(N + 1);
    auto sieve = [&](int n)
    {
        st[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            if (!st[i])
                prime[cnt++] = i;
            for (int j = 0; i * prime[j] <= n; j++)
            {
                int t = i * prime[j];
                st[t] = 1;
                if (i % prime[j] == 0)
                    break;
            }
        }
    };
    sieve(N);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<vector<int>> dp(2, vector<int>(N + 1));
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= N; j++)
        {
            dp[i & 1][j] = dp[(i - 1) & 1][j];
            if ((j ^ a[i]) <= N)
            {
                dp[i & 1][j] = (dp[i & 1][j] + dp[(i - 1) & 1][j ^ a[i]]) % mod;
            }
        }
    }
    int res = 0;
 
    for (int i = 1; i <= N; i++)
    {
        if (!st[i])
            res = (res + dp[n & 1][i]) % mod;
    }
 
    cout << res << endl;
}

回到正题

正常写暴力dp的话 dp[i][j][k]表示前 i 个 异或值为 j 此时背包容量为 k 是否存在

转移： dp[i][j][k]|=dp[i-1][j^w][k-a[i]] 这样n三方的复杂度肯定不行

考虑优化 因为背包容量最大为1024 所以考虑用到bitset优化

将第三维背包容量往后调到dp值上

dp[i][j] 表示前 i 个 异或值为 j 背包容量的集合

集合？比如011101 就是异或和为j 的可能背包容量为 0 2 3 4 [左移所少位背包容量就是多少]

初始背包容量为0 二进制下也就是第一位为1

背包容量加上v就是向左移动v位即可

最后从大到小枚举异或和 在满背包的情况下 即第m位为1

bitset真的很好用 ！！！

当转移只有 i 和 i-1 的时候 用滚动数组优化

一定是用滚动数组！！！ 不要轻易的将第一维消掉！！！！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1050;

bitset<maxn>f[2][maxn];

int main(){

    IOS

    int t;
    cin>>t;

    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=0;i<1024;i++)f[0][i].reset();
        f[0][0].set(0);
        for(int i=1;i<=n;i++){
            int v,w;
            cin>>v>>w;
            for(int j=0;j<1024;j++){
                f[i&1][j]=f[(i&1)^1][j]|(f[(i&1)^1][j^w]<<v);
            }
        }
        int ans=-1;
        for(int i=1023;i>=0;i--){
            if(f[n&1][i][m]){
                ans=i;
                break;
            }
        }
        cout<<ans<<endl;
    }
}

D Ball

题意：

有n个点在棋盘上，请找到一个三元组使得三个点之间距离的中位数是个素数。其中距离指的是哈密顿距离。

dist = (abs(x1 - x2) + abs(y1 - y2))

分析：

数据最多满足n方的复杂度 所以先枚举两两点的距离 再从小到大排序

开始枚举已经排好序的边

对于一条边<a,b> 使他为中位数 要找出前面出现的点到a/b 后面还没出现的点到b/a 的个数

因为前面出现的点是集合的形式 考虑用bitset

p[i]表示已经出现到 i 的点的集合

a和b不能同时出现 已经更新了的点 [因为要保证当前边一定是中位数]

p[i] xor p[j] 即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <bitset>

using namespace std;
const int N = 2010;
int n, m, a[N], b[N];
bitset<N> p[N];
struct Edge
{
    int a, b, w;
    bool operator < (const Edge &t) const
    {
        return w < t.w;
    }
}edges[N * N];
bool st[N * N];
int primes[N * N], cc;
int cnt, ans;

void init()
{ // 线性筛法
    for(int i = 2 ; i < 200010 ; i ++ )
    {
        if(!st[i]) primes[cnt ++ ] = i;
        for(int j = 0 ; primes[j] * i < 200010 ; j ++ )
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int calc(int i, int j)
{
    return abs(a[i] - a[j]) + abs(b[i] - b[j]);
}

void solve()
{
    cin >> n >> m;
    cnt = 0, ans = 0;
    for(int i = 0 ; i <= n ; i ++ ) p[i].reset();
    for(int i = 1 ; i <= n ; i ++ ) cin >> a[i] >> b[i];
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = i + 1; j <= n ; j ++ ) 
            edges[++ cnt] = {i, j, calc(i, j)};
    sort(edges + 1, edges + cnt + 1); // 按距离排序，先枚举的边一定比当前的小，做好标记即可。
    for(int i = 1 ; i <= cnt ; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if(!st[w]) ans += (p[a] ^ p[b]).count(); // p[a]表示距离比w小的点的数量 ， st表示他是不是素数
        p[a][b] = 1, p[b][a] = 1;
    }
    cout << ans << endl;
}

int main()
{
    init();
    int T = 1;
    cin >> T;
    while(T -- ) solve();
    return 0;
}

H Path

题意：

最短路问题，给定一个带权有向图，其中包含特殊边和普通边，特殊边的特殊之处在于我们经过特殊边之后对于不相邻的点我们可以

免费传送过去，不花费时间，对于相邻的边花费时间w[i] 变成w[i] - k，但是不是永久-k只是在经过这条边之后，最后请问从起点到

所有点的最短距离。

分析：

很明显 最短路数组dis[t][0/1]表示上一步是普通边还是特殊边到t的最短距离

关键点在于 特殊边是能够到达任意一点的 不可能每次都枚举

利用最短路的性质 我们枚举只用枚举还没到达过的点 可以用set维护

转移

如果是普通边 直接转移就好

如果是特殊边 转移集合里非相临边 相临边按照普通边-k转移就好

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>

using namespace std;
#define int long long
const int N = 5e5 + 10, M =  N * 2, INF = 1e18;
int n, m, s, k;
int h[N], ne[M], e[M], w[M], p[M], idx;
struct Node
{
    int a, d, p;
    bool operator < (const Node &t) const
    {
        return d > t.d;
    }
};
bool st[N][2];
int dist[N][2];
int gg[N]; // 标记

void add(int a, int b, int c, int d)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, p[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs()
{
    set<int> S;
    for(int i = 1 ; i <= n ; i ++ )
    {
        if(i != s) S.insert(i);
        st[i][0] = st[i][1] = false;
        dist[i][0] = dist[i][1] = INF;
    }
    dist[s][0] = 0;
    priority_queue<Node> q;
    q.push({s, 0, 0});
    int cnt = 0;
    while(q.size())
    {
        auto t = q.top();
        int ty = t.p, ver = t.a;
        q.pop();
        cnt ++ ;
        if(!ty) S.erase(ver);
        else
        {
            for(int i = h[ver] ; ~i ; i = ne[i])
            {
                int j = e[i];
                gg[j] = cnt; // 这个点是邻边
            }
            vector<int> temp;
            for(auto it : S)
            {
                if(gg[it] != cnt) // 没有被遍历的非相邻的点
                {
                    temp.push_back(it);
                    dist[it][0] = dist[ver][ty];
                    q.push({it, dist[it][0], 0});//相当于添加源点
                }
            }
            for(auto it : temp) S.erase(it); // 被更新的点被遍历过 所以直接删除
        }
        
        int y = 0;
        if(ty) y -= k;

        if(st[ver][ty]) continue; 
        st[ver][ty] = true;
        for(int i = h[ver] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(dist[j][p[i]] > dist[ver][ty] + w[i] + y)
            {
                dist[j][p[i]] = dist[ver][ty] + w[i] + y;
                q.push({j, dist[j][p[i]], p[i]});
            }
        }
    }
}   

void solve()
{
    cin >> n >> m >> s >> k;
    for(int i = 0 ; i <= n ; i ++ ) h[i] = -1, gg[i] = 0;
    idx = 0;
    for(int i = 1 ; i <= m ; i ++ )
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
    }
    
    bfs();
    for(int i = 1 ; i <= n ; i ++ ) 
        if(min(dist[i][0], dist[i][1]) == INF) cout << -1 << " ";
        else cout << min(dist[i][0], dist[i][1]) << " ";
    cout << endl;
}

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

标签：杭电多校,const,int,cin,long,2022,include,define
From： https://www.cnblogs.com/wzxbeliever/p/16737395.html

相关文章

  • 开学总动员！2022华为开发者大赛等你来挑战！
    摘要：9月23日开启2022华为开发者大赛“开学季总动员”主题直播活动。金秋开学季，为了吸引更多高校开发者关注与参与华为开发者大赛，华为于9月23日开启2022华为开发者大赛“开......
  • serialportscreeen-2022-09-27
    1、继续单元格反色问题，因为大的表格包含许多小的单元格，因此在工程中通过一个反色单元格占用一个背景图片，然后在变量数据录入过程选择好页面切换，如果所需表格很多，就需要考虑......
  • 2022年09月22日11:43:20
    1、rviz-d[文件名]使用指定的配置文件打开rviz-d/home/ubuntu/work/bkth/ros_ws/src/RFans_Rviz_cfg.rviz2、rviz-f【frame名】接收指定的framerviz-fworld......
  • Jenkins 20220927笔记本4
                          ......
  • 互联网摸鱼日报（2022-09-28）
    互联网摸鱼日报（2022-09-28）InfoQ热门话题靠谱CTO必须是技术高手？前Facebook总监：技术越好，bug越少TDSQL破局敏态业务背后的技术演进|DBTalk技术公开课第3期在敏......
  • English words chapter 20220927
    ......
  • 20222.9.27-代码大全-9月读后感1
    近期，我阅读了这本书的一切皆有可能这一部分。这本书的作者在出版这本书的时候，遇到了各种各样的麻烦，但是由于他坚信一切皆有可能的观点，克服了重重困难，这本书终于得到了出版......
  • CSP 2022 备战 时间复杂度
    如果我们要对一个程序进行评级，可以通过什么？最显著的，自然是通过测试点评价其次，就是通过时间复杂度与空间复杂度来评级了由于空间一般是十分充足的，UKE的报错情况少之又少......
  • Test 2022.09.27
    今天不知道是什么专场了，但是我知道的是我今天真的没有改完！！！！太气了，最短路的赋值号写成大于竟然不会报错，害得我改了半个下午一个晚上，lz快要崩溃了T1Windy数简简单单数位dp，......
  • 2022.9.18训练赛
    2019江西省赛-VirtualJudge(csgrandeur.cn)    ......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99