首页 > 其他分享 >2022 HDU多校1

2022 HDU多校1

时间:2022-08-20 16:04:09浏览次数:66  
标签:HDU le const Point int text 多校 cin 2022

String(扩展KMP、差分)

Problem

给定一个字符串\(S\),定义\(F_S\)表示满足如下条件的正整数\(x\)的数量

  • \(1\le x\le |S|\)
  • \(S[1,\cdots,x]=S[|S|-x+1,|S|]\)
  • \(S[1,\cdots,x]\)和\(S[|S|-x+1,|S|]\)的交的长度不为\(0\)且可以被\(k\)整除

现在要求\(\prod_{i=1}^{|S|}(F_{S[1,\cdots,i]}+1)\)

\(1\le |S|\le 10^6\)

Solve

image

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        string s;
        cin>>s;
        int n=s.size();
        int k;
        cin>>k;
        vector<int>z(n),sum(n+1);
        z[0]=n;
        for(int i=1,l=0,r=0;i<n;i++){
            if(i<=r && z[i-l]<r-i+1) z[i]=z[i-l];
            else z[i]=max(0,r-i+1);
            while(i+z[i]<n && s[z[i]]==s[i+z[i]]) ++z[i];
            if(i+z[i]-1>r) l=i,r=i+z[i]-1;
        }
        ll ans=1;
        for(int i=0;i<n;i++){
            int x=z[i];
            if(x>=i+k){
                x=((x-i)/k)*k;
                sum[2*i+k]++;
                if(2*i+k+x<=n) sum[2*i+k+x]--;
            }
        }
        for(int i=1;i<=n;i++){
            if(i+k<=n) sum[i+k]+=sum[i];
            ans=ans*(sum[i]+1)%mod;
        }
        cout<<ans<<'\n';
    }
}

Dragon slayer(暴力枚举判断、模拟)

Backpack(背包、bitset 优化空间、暴力)

Problem

有\(n\)个物品,每个物品有价值\(v\)和重量\(w\),现在有一个背包容量为\(m\),问在把背包刚好装满的情况下,物品价值异或值最大是多少

\(1\le n,m\le 2^{10}\)

\(1\le v,w\le 2^{10}\)

Solve

这题会卡空间,首先很容易想到\(O(n^3)\)的做法,用\(dp[i][j]\)表示背包容量为\(i\),价值异或和为\(j\)是否可以转移到,用滚动数组优化一下,就是

dp[2][i][j];
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
   for(int j=w[i];j<=m;j++)
	for(int j=0;j<=1024;j++)
	dp[1][j][k]|=dp[0][j-w[i]][k^v[i]];
}

但这样空间会炸,所以考虑用bitset优化

Code

#include <bits/stdc++.h>
using namespace std;
int main(){
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     int T;
     cin>>T;
     while(T--){
     	int n,m;
     	cin>>n>>m;
     	vector<bitset<1024>>f1(1024),f2(1024);
        f1[0][0]=1;
     	for(int i=1;i<=n;i++){
     		int v,w;
     		cin>>v>>w;
     		for(int j=0;j<1024;j++){
               f2[j]=f1[j]|(f1[j^w]<<v);
     		}
     		for(int j=0;j<1024;j++)
     		   f1[j]=f2[j];
     	}
     	bool ok=0;
     	for(int i=1023;i>=0;i--){
     		if(f1[i][m]){
     			cout<<i<<'\n';
     			ok=1;
     			break;
     		}
     	}
     	if(!ok) cout<<-1<<'\n';
     }
}

Ball(bitset优化)

Problem

在\(M\times M\)的平面上有\(N\)个点,求有多少三个无序点对的曼哈顿距离的中位数是质数

曼哈顿距离:\(|x_1-x_2|+|y_1-y_2|\)

\(1\le N\le 2000\),\(1\le M\le 10^5\)

Solve

暴力做法是\(O(n^3)\)的,这种问题一般先转化成求每个是素数的距离对答案的贡献。我们先把所有二元点对按照距离排序,有\(O(n^2)\)个,然后按照距离从小到大考虑。由于我们从小到大考虑,并且求的是中位数,所以我们需要知道对于当前的边的两个点\(u,v\),有多少个点到达\(u\)的距离小于当前距离,有多少个点的距离到达\(v\)大于当前距离(反过来考虑也是一样的)。注意到我们从小到大枚举,那么在之后的枚举过程中,之前的边都会小于当前边,所以我们在枚举过程中更新"有多少个点到达\(u\)的距离小于当前距离",而这里的当前距离是对于后面边而言。而"有多少个点的距离到达\(v\)大于当前距离"我们在加边的时候更新,而后面枚举距离的时候不断减小这个点集的数量。类似于双指针的思想。更新过程和求点数过程都是\(O(\frac{n}{w})\),故总时间复杂度是\(O(\frac{n^3}{w})\)

具体求点数就是\((\text{large}[u]\&\text{small}[v]).count()\),这样表示\(u,v\)都能到达的点,并且满足到\(u\)的距离大于当前边,到\(v\)的距离小于当前边。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int M=2e5+10,N=2005;
int primes[M],st[M],cnt;
void get_prime(){
	st[1]=1;
	for(int i=2;i<=200000;i++){
		if(!st[i]) primes[++cnt]=i;
		for(int j=1;j<=cnt&&primes[j]*i<=200000;j++){
            st[primes[j]*i]=1;
            if(i%primes[j]==0) break;
		}
	}
}
struct edges{
	int u,v,dis;
	bool operator < (const edges &t)const{
		return dis<t.dis;
	}
}e[N*N];
bitset<2005>small[2005],large[2005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	get_prime();
	while(T--){
         int idx=0;
		int n,m;
		cin>>n>>m;
		vector<int>x(n+1),y(n+1);
		for(int i=1;i<=n;i++){
              cin>>x[i]>>y[i];
              small[i].reset(),large[i].reset();
		}
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++){
				int dis=abs(x[i]-x[j])+abs(y[i]-y[j]);
				e[++idx]={i,j,dis};
				large[i].set(j),large[j].set(i);
			}
	    sort(e+1,e+1+idx);
        ll ans=0;
        for(int i=1;i<=idx;i++){
        	int u=e[i].u,v=e[i].v,dis=e[i].dis;
        	if(!st[dis]) ans+=(large[u]&small[v]).count()+(large[v]&small[u]).count();
        	large[u].set(v,0),large[v].set(u,0);
        	small[u].set(v,1),small[v].set(u,1);
        }
        cout<<ans<<'\n';
	}
	return 0;
}

Travel plan(图论、莫比乌斯反演、数论)

Treasure(克鲁斯卡尔重构树)

Path(图论、分层图、BFS)

Problem

给定\(n\)个点\(m\)条边的有向图,每条边有边权,其中有一些特殊边和普通边,如果\(u\)经过特殊边到达\(v\),那么下次\(v\)可以到达任意点,如果这个点不与\(v\)相邻,那么花费\(0\),如果和\(v\)相邻,假设邻边的边权为\(w\),那么花费\(w-k\)。问从\(S\)出发,把每个点都遍历一遍,每个点需要的最少花费是多少,如果不能遍历到,输出\(-1\)。

\(1\le n,m\le 10^6\)

Solve

  • 分层图
  • BFS

在\(BFS\)队列中,记录每个点上一次是由什么边转移过来的,类似于分层图的思想,根据转移过来边的类型分类进行下一步转移。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
const ll inf=1e18;
struct edges{
	int v,w,t,nxt;
}e[N];
int head[N],cnt,tag[N];
void add(int u,int v,int w,int t){
	e[cnt]={v,w,t,head[u]},head[u]=cnt++;
}
struct node{
	int u; ll d; int p;
	bool operator < (const node&t)const{
		return d>t.d;
	}
};
ll dist[N][2];
bool st[N][2];
int n,m,S,K;
void bfs(){
	set<int>s;
	for(int i=1;i<=n;i++){
		if(i!=S) s.insert(i);
        dist[i][0]=dist[i][1]=inf;
        st[i][0]=st[i][1]=false;
	}
	priority_queue<node>q;
	q.push({S,0,0});
	dist[S][0]=0;
	int idx=0;
	while(q.size()){
		auto t=q.top();
		int u=t.u;
		q.pop();
		idx++;
		if(!t.p) s.erase(u); //由普通路径更新得到,直接删除
		else{   //上一次的点是经过特殊边得到的,那么它下次可以到达任意点,这里先转移与它不相邻的点
           for(int i=head[u];~i;i=e[i].nxt){
           	 int v=e[i].v;
           	 tag[v]=idx;  //把与经过特殊边得到的点的相邻点标记
           }
           vector<int>tt;
           for(auto v:s){  //更新所有没有更新过并且不与当前点相邻的点
           	 if(tag[v]!=idx){
           	 	tt.push_back(v);
           	 	dist[v][0]=dist[u][0]; 
           	 	q.push({v,dist[v][0],0}); //重置为不是由特殊边更新得到
           	 }
           }
           for(auto v:tt) s.erase(v); //更新了,在待更新队列中删除
		}
	    int delta=0;
	    if(t.p) delta-=K;
	    if(st[u][t.p]) continue;
	    st[u][t.p]=true;
	    //更新邻边的点(普通边和特殊边一起考虑)
	    for(int i=head[u];~i;i=e[i].nxt){
	    	int v=e[i].v,w=e[i].w,type=e[i].t;
	    	if(dist[v][type]>dist[u][t.p]+w+delta){
	    		dist[v][type]=dist[u][t.p]+w+delta;
	    		q.push({v,dist[v][type],type});
	    	}
	    }
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
    cin>>T;
    while(T--){
       memset(head,-1,sizeof head);
       memset(tag,0,sizeof tag);
       cnt=0;
       cin>>n>>m>>S>>K;
       for(int i=1;i<=m;i++){
       	int u,v,w,t;
       	cin>>u>>v>>w>>t;
       	add(u,v,w,t);
       }
       	bfs();
       	for(int i=1;i<=n;i++){
       	   ll d=min(dist[i][0],dist[i][1]);
           if(d==inf)  cout<<-1<<" ";
           else cout<<d<<" ";
       	}
       	cout<<'\n';
    }
}

Laser(计算几何、暴力check)

Problem

二维平面上有\(n\)敌人,现在可以在任何一个位置放置一个激光发射器,这个激光发射器会以米字的形式发出激光,在激光上的敌人会被消灭,询问是否可以只放置一个激光发射器就把所有敌人消灭

\(1\le n\le 5\times 10^5\)

Solve

激光发射方向有\(4\)个,即横线 竖线 右斜线 左斜线。如果存在这样一个点,那么每个敌人肯定在这个点的某一个方向上,由于两条直线可以确定一个点,可以暴力枚举这两个条线然后暴力判断。可以先确定第一个点所在的直线,然后找到一个和它不在一条直线上的点\(k\),再枚举点\(k\)所在的直线,现在就有两个直线了,可以确定一个激光点,然后再去判断剩下\(n-2\)个点是否在激光点的\(4\)个方向上即可。
image

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+10;
struct Point{
	int x,y;
	Point(){}
	Point(int x_,int y_):x(x_),y(y_){}
	Point operator + (const Point &t)const{
		return {x+t.x,y+t.y};
	}
	Point operator - (const Point &t)const{
		return {x-t.x,y-t.y};
	}
	double operator * (const Point&t)const{
		return x*t.x+y*t.y;
	}
	double operator ^ (const Point&t)const{
		return x*t.y-y*t.x;
	}
	Point operator * (const double t)const{
		return {x*t,y*t};
	}
}p[N];
//横线 竖线 右斜线 左斜线
Point d[]={{0,1},{1,0},{1,1},{1,-1}}; //点向式表示直线
int n,k;

bool check(Point c){
	for(int i=2;i<=n;i++){
		if(i==k) continue;
        int dx=p[i].x-c.x,dy=p[i].y-c.y;
        if(abs(dx)!=abs(dy) && dx*dy!=0) return false;    
	}
	return true;
}
//点向式
Point get_intersection(Point p1,Point v1,Point p2,Point v2){
	Point u=p1-p2;
	double t=(v2^u)/(v1^v2);
	return p1+v1*t;
}
bool solve(){
	
	for(int i=0;i<4;i++){
		for(k=2;k<=n;k++){
			if(((p[k]-p[1])^d[i])!=0){ //点k和点1不在一条直线上
                 break;
			}
		}
		if(k==n+1) return true; 
		for(int j=0;j<4;j++){ //枚举点k所在的直线
            if(i==j) continue;
            Point c=get_intersection(p[1],d[i],p[k],d[j]);
            if(check(c)) return true;
		}

	}
	return false;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--){
      cin>>n;
      for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
      if(solve()) cout<<"YES\n";
      else cout<<"NO\n";
	}
}

Random(概率论)

Problem

\(n\)个实数在区间\([0,1]\)中随机生成,接着进行\(m\)次操作,每次操作有\(\frac{1}{2}\)的概率删掉最大的数,有\(\frac{1}{2}\)的概率删掉最小的数。求最后剩下的数的和的期望。

Solve

\(E(x)=\int_0^1x\cdot 1dx=\frac{1}{2}\),从\(n\)个数中随机以\(\frac{1}{2}\)的概率\(m\)次删掉最大数或最小数,可以看做随机选择了\(n-m\)个数。期望总和写成\(\sum_{i=1}^{n-m}a_ip_i\),这是什么形式?就是期望啊,所以答案就是\(\frac{n-m}{2}\)

Code

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int T;
   cin>>T;
   int inv2=mod/2+1;
   while(T--){
   	int n,m;
   	cin>>n>>m;
    cout<<1LL*(n-m)*inv2%mod<<'\n';
   }
   return 0;
}

Alice and Bob(博弈论)

Problem

一开始黑板上有\(n+1\)个数,现在\(\text{Alice}\)和\(\text{Bob}\)轮流操作。\(\text{Alice}\)每次可以把黑板上还有的数分成\(2\)部分,\(\text{Bob}\)可以在\(\text{Alice}\)分成的\(2\)份中选择一份从黑白上擦除,然后把另一部分的数都减\(1\)。如果黑板上出现数字\(0\)则\(\text{Alice}\)赢,如果\(\text{Bob}\)把数字都擦除完了,那么\(\text{Bob}\)赢。

Solve

博弈问题一般先考虑最小的必胜态或必败态。容易发现只有\(1,1\)时是必胜态,\(2,2,2,2\)是必胜态,因为$$\text{Alice}\(可以平分然后\)\text{Bob}$无论如何操作都会变成\(1,1\)这个必胜态。

发现如果有\(2^i\)个\(i\),相当于一个\(i\),只需判断最后能否得到\(0\)即可。

Code

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		vector<int>a(n+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\n";
	    else cout<<"Bob\n";
	}
}

标签:HDU,le,const,Point,int,text,多校,cin,2022
From: https://www.cnblogs.com/Arashimu0x7f/p/16607888.html

相关文章

  • NOIP2022模拟赛二 By ZJ 8.20
    Preface昨天睡得有点晚因此今天脑子不是很清醒……T1本来一眼秒了的,结果自己数\(n=4\)的个数的时候输错了就以为自己错了后来写了个假算法发现全场就我没过T1:(A.「NOI......
  • Adobe Bridge 2022 for mac(br2022)资源管理软件
    Bridge2022mac版更新了,这是一款Adobe系列的资源管理软件,它拥有强大的媒体集中资产访问功能:可以查看、搜索、排序、管理和处理图像文件。软件可以使用高级过滤器、集合和......
  • lvgl在vs2022上的使用
    下载源码:https://github.com/fanlulin/lv_port_win_visual_studio.git使用git命令下载,下载之后,需要注意lvgl文件夹是否为空,为空则需要重新拉取打开.sln文件,选择vs2022......
  • 2022-08-15 吉林化工学院 第五组 韩嘉宁(MySQL基础)
    掌握情况:已全部理解并且应用基本熟练。学习心得:难得的轻松!!!但基本都是理论知识,需要加强记忆理解!Mysql数据库目录掌握情况:已全部理解并且应用基本熟练。学习心得:难得的轻......
  • 2022/8/20 总结
    A.P4398[JSOI2008]BlueMary的战役地图考场写了个暴力,我还以为要挂了,结果这题暴力可过;Solution本来想写\(\mathtt{O(n^6)}\)的暴力,但感觉可能过不了,所以加了亿点......
  • "蔚来杯"2022牛客暑期多校训练营4
    A.TaskComputing给定\(n\)个任务,每个任务有两个权值\(w_i,p_i\),从中按任意顺序选出\(m\)个任务\((a_1,a_2,...,a_m)\),收益为\(\sum\limits_{i=1}^mw_{a_i}\prod\limits_{......
  • 在Ubuntu20.04上使用kubeadm搭建k8s集群(2022年8月版本为v1.24.4)
    1.一些真心话在开始之前,需要将重要的事情说三遍:一定要认真阅读官方文档!一定要认真阅读官方文档!!一定要认真阅读官方文档!!!我在搭建k8s之前看了网上很多教程,也尝试的执行了......
  • 2022-8-20 每日一题-二叉树-递归
    654.最大二叉树难度中等499收藏分享切换为英文接收动态反馈给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:创建一个......
  • 2022/8/20暑假学习日记
    1问题:合格的软件工程师,有什么具体的标准吗?还是说能写代码,又能发现问题解决问题就可以成为了呢?我们现阶段可以从哪方面开始培养自己的开发思维和能力,向工程师迈进?回答:作为......
  • 2022-8-20 剑指offer-滑动窗口+(桶排序或者有序集合)
    剑指OfferII057.值和下标之差都在给定的范围内难度中等55收藏分享切换为英文接收动态反馈给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在......