Logo zibenlun 的博客

博客

标签
暂无

为了庆祝 Atcoder 上绿写一篇题解吧

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-24 21:32:58

题目链接

比较水的交互题

Solution

题目大意就是让你用最少的朋友验证出坏了的橙汁。

题目中比较关键的在于只有一杯坏掉的橙汁，所以我们可以想到用二进制来表示每一杯橙汁的编号，经过询问后再把所有喝到坏橙汁的朋友转换成二进制，就可以查询到哪一杯橙汁是坏的。

小细节

  • 想要知道 $n$ 杯橙汁的情况，我们其实只需要知道其中的 $n-1$ 杯就行。因为前 $n-1$ 杯要是有坏的，最后一杯一定不是坏的，反之最后一杯一定是坏的。

  • 橙汁的编号一定不能从零开始，如果第 $0$ 杯是坏掉的，那么我们也无法判断。

  • 其余的细节放在代码注释中了。

#include<bits\/stdc++.h>
using namespace std;
vector<int> v[100005];
int n,lg,u=1; 
int main(){
	cin>>n;
	while(u*2<=n){
		u*=2;
		lg++;
	}
	cout<<lg+(u!=n)<<endl;\/\/不能正好满一位，再额外加一位 
	for(int i=1;i<=n-1;i++){
		int cnt=0,x=i;
		while(x){
			x>>=1;
			cnt++;
		}\/\/预处理这一杯橙汁的位数 
		x=i;
		for(int j=1;x;j++){
			if(x&1) v[j].push_back(i);\/\/统计每一个人需要喝哪几杯 
			x>>=1;
		}
	}
	for(int i=1;i<=lg+(u!=n);i++){
		cout<<v[i].size();
		for(auto j:v[i]) cout<<" "<<j;
		cout<<endl;
	}
	int pos=0,ans=0;
	for(int i=1;i<=lg+(u!=n);i++){
		char c;
		cin>>c;
		int x=c-'0';
		ans+=(1<<pos)*x;\/\/转换回杯子的编号 
		pos++;
	}
	if(ans!=0) cout<<ans<<endl;
	else cout<<n<<endl;
	return 0;
}

AT_abc337_d 题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-25 11:24:42

题目大意：

给你一个矩阵，求出还需要修改多少个点就可以满足有 $K$ 个连续的 $O$ （只能是横向或者纵向）。 其中只可以修改 $·$ ，不能修改 $X$ 。

Solution

首先我们分为两步来进行计算。

横向

对于每一行我们可以用一个队列进行统计，一开始在队列中放入前 $K$ 个元素，然后我们不断向右移动，每一次移动把最头上的出队，最后面的入队，同时我们统计出当前的队列中有多少 $O$ 以及有没有 $X$ 。如果没有 $X$ ，那么就统计所需最少的变化次数。

纵向

方法相同就不再说了。

小细节

$H W$的范围是通过乘积的方式给出，所以我们开数组的时候要动态开，可以有三种选择：

  1. 在主函数中根据 $H W$ 的值来开数组

string

vector

CODE


#include<bits\/stdc++.h>
using namespace std;
int ans=0x3f3f3f3f,n,m,k;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	char a[n+5][m+5];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	if(m>=k){
		for(int i=1;i<=n;i++){
			queue<char> q;
			int flag=0,sum=0;
			for(int j=1;j<k;j++){
				if(a[i][j]=='x') flag++;
				if(a[i][j]=='.') sum++;
				q.push(a[i][j]);
			}
			for(int j=k;j<=m;j++){
				q.push(a[i][j]);
				if(a[i][j]=='x') flag++;
				if(a[i][j]=='.') sum++; 
				if(flag==0){
					ans=min(ans,sum);
				}
				if(q.front()=='x') flag--;
				if(q.front()=='.') sum--;
				q.pop();
			}
		}		
	}
	if(n>=k){
		for(int i=1;i<=m;i++){
			queue<char> q;
			int flag=0,sum=0;
			for(int j=1;j<k;j++){
				if(a[j][i]=='x') flag++;
				if(a[j][i]=='.') sum++;
				q.push(a[j][i]);
			}
			for(int j=k;j<=n;j++){
				q.push(a[j][i]);
				if(a[j][i]=='x') flag++;
				if(a[j][i]=='.') sum++; 
				if(flag==0){
					ans=min(ans,sum);
				}
				if(q.front()=='x') flag--;
				if(q.front()=='.') sum--;
				q.pop();
			}
		}		
	}
	if(ans!=0x3f3f3f3f) cout<<ans;
	else cout<<-1;
	return 0;
}

P10114

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-28 20:40:09

思路

看到 $100%$ 的数据范围很吓人对吧，不过经过优化的 $n^2$ 的时间复杂度也是可以完成的。

暴力的方法不细说，就是直接按照题目要求模拟一下。

再看子任务三，$d_i$ 是 $2$ 的次幂，众所周知，指数的增长是非常快的，即使在长整型中也只有不到 $64$ 次，所以一定会有很多重复。针对这个特性我们可以想到把相同的值只保留一个并统计个数，之后在计算的过程中，对于每一个 $(i,j)$ 我们在统计一遍的个数上乘上 $d_i$ 和 $d_j$ 的个数。

对于全部的数据其实差不多，也是子任务三的思路，但是要加上一点点优化。我们能发现，对于不等的一对 $(i,j)$ ,实际上 $(i,j)$ 与 $(j,i)$ 时的结果相同，那么我们只统计一次再乘二就可以了。

CODE

#include<bits\/stdc++.h>
using namespace std;
inline __int128 read() {
	__int128 s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s;
}
#define lowbit(x) (x&(-x))
inline void write(__int128 x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x\/10);
	putchar(x%10+'0');
}
long long n,a[2000005];
__int128 ans;
bool cmp(int x,int y){
	return x>y;
}
map<long long,int> mp,vis;
int main() {
\/\/	freopen(".in","r",stdin);
\/\/	freopen(".out","w",stdout);
	n=read();
	int m=n;
	for(int i=1;i<=m;i++){
		a[i]=read();
		if(mp[a[i]]>=1){
			m--;
			i--;
			mp[a[i+1]]++;
			continue;
		}
		mp[a[i]]=1;
	}
	for(int i=1;i<=m;i++){
		for(int j=i;j<=m;j++){
			long long x=a[i]+a[j],sum=0;
			while(x) x-=lowbit(x),sum+=1+(i!=j);
			x=a[i]-a[j];
			if(x<0) x=-x;
			while(x) x-=lowbit(x),sum+=1+(i!=j);
			ans+=sum*mp[a[i]]*mp[a[j]];
		}
	}
	write(ans);
	return 0;
}

AT_abc341_e

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-18 15:37:02

思路

题目大意就是可以反转一段区间或查询一段区间中有没有连续的字符。根据题意我们可以维护每两个字符之间是否相等。在修改时可以发现如果两个字符都在区间内，那么其关系不变。所以对于每一次修改我们只需要维护两端的字符之间关系的变化。实现过程中可以使用集合储存所有相邻且相同的字符，最后用二分查询即可。

CODE

#include<bits\/stdc++.h>
#define int long long
using namespace std;
set<int> ss;
string s;
int n,q;
int vis[5000005];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>s;
	s=" "+s;
	for(int i=1;i<n;i++){
		if(s[i]==s[i+1]){
			vis[i]=1;
			ss.insert(i);
		}
	}
	for(int i=1;i<=q;i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			if(x-1!=0){
				if(vis[x-1]){
					vis[x-1]=0;
					ss.erase(x-1);
				}
				else {
					vis[x-1]=1;
					ss.insert(x-1);
				}				
			}
			if(vis[y]){
				vis[y]=0;
				ss.erase(y);
			}
			else {
				vis[y]=1;
				ss.insert(y);
			}
		}
		else {
			int z=*ss.upper_bound(x-1);
			if(z<y&&z>=x){
				cout<<"No\n";
			}
			else {
				cout<<"Yes\n";
			}
		}
	}
	return 0;
}

AT_abc341_d

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-18 15:46:28

思路

题目给出的数据范围很大，所以只能考虑二分，这里我们直接二分答案。对于我们二分出的值，可以通过 mid\/n 和 mid\/m 求出在它以内分别有多少个 $n$ 和 $m$ 的倍数，之后我们减去重复的，剩下的就是这个数的位次。

重复的部分实际上就是 $n$ 和 $m$ 的最小公倍数。

CODE

#include<bits\/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	int x=n*m\/(__gcd(n,m));
	int l=0,r=1e18;
	int ans=1e18;
	while(l<=r){
		int mid=(l+r)\/2;
		int sum=mid\/n+mid\/m-mid\/x-mid\/x;
		if(sum>=k){
			r=mid-1;
			ans=min(ans,mid);
		}
		else {
			l=mid+1;
		}
	}
	cout<<ans;
	return 0;
}

山东省青少年创意编程与智能设计大赛游记

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-21 18:03:35

前一天

早上七点就起来了，但是八点半才出门，中午到了酒店就点了个外卖。下午本来计划着要去滑雪，但是懒得出门了，就在宾馆里颓了一下午。晚上吃了个火锅就接着颓。

比赛当天

6点起来发现没有地方吃早餐，去楼下便利店吃了个关东煮。七点到了历二（谁家比赛七点签到），碰到了小学的微机老师。八点先做了 40 分钟的笔试，100道题只做了40道，剩下的全蒙了一遍。之后休息十分钟，上了个厕所又写了一下板子（写完才知道可以提前准备好直接粘下来）。上来 20 分钟秒了T1，T2 。感觉前两天纯纯签到题，但是之后两题突然上难度。T3 上来先写了30分的暴力（带一点优化），之后改了半天也没拿到另外两组特殊点（个人认为很好拿，但是没拿到，很郁闷）。好像是十点多开始写T4 。还是先拿了 30 分（用的是树上差分，后来又改成了类似于异或思路的解法，做树上边权的合并，并删掉两者的最小公倍数），感觉自己不算暴力，但是没有 AC 。结束前突然想起之前写过的一道题（好像是luogu月赛的）用过用 set 和 map 维护相同的数来统计个数，试了一下提到了 50 分。到此一共 280 分，自己觉得不少了，所以直接交卷走人了。

回到候场大厅，发现竟然有实时榜单（给家长看的），竟然拿了 rk2 也是很震惊，rk1 就比我高了 10 分，T4也没有我高，自己感觉T4能那个全场最高吧。家长还没来，就和小学的微机老师聊了几句。

出了历二，准备回潍坊，一开始高速还没有封，等到我们去了，已经封了路，之后返回城区里面，又去了万象城看了看，又找了家酒店，希望明天能回去吧。

题解：P10270 好奇心宝贝

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-25 09:01:00

思路

首先我们将整个矩形按照与起点的距离分成不同的层，我们可以发现只要这一层有两个以上的不同的字母，那么我们在走到这一层的时候一定可以使这一位不同，所以我们就只需要找到最小的有多于一种字母的层数就行了。时间复杂度 $O(n^2)$。

代码

#include<bits\/stdc++.h>
#define ll long long
#define int long long
#define int_128 __int128
#define lowbit(x) (x&(-x))
using namespace std;
set<int> s[4005];
int n,m;
char a[2005][2005];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			s[i-1+j-1+1].insert(a[i][j]);
		}
	}
	for(int i=1;i<=n+m-1;i++){
		if(s[i].size()>1){
			cout<<i-1;
			return 0;
		}
	}
	cout<<n+m-1;
	return 0;
}

题解：AT_abc347_d [ABC347D] Popcount and XOR

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-31 09:37:49

解决

题意

您将得到非负整数 $a$ 、 $b$ 和 $C$ 。

确定是否有一对非负整数 $(X, Y)$ 满足以下所有五个条件。如果存在这样的对，则打印一个。

  • $0 \le X \lt 2^{60}$

  • $0 \leq Y \lt 2^{60}$

  • $\operatorname{popcount}(X) = a$

  • $\operatorname{popcount}(Y) = b$

  • $X \oplus Y = C$

思路

首先要满足 $X \oplus Y = C$ 我们需要在把 $C$ 转化成二进制后的所有位在 $X$ 和 $Y$ 中出现仅一次。那么 $X$ 和 $Y$ 的其余的位 只需要根据 $a$ 和 $b$ 的大小都选或者都不选即可。

细节

  • 判断当 $a$ 和 $b$ 的位数减去构成 $C$ 要用的位数后如果是奇数个，那么说明之后不能通过选取同一个位数相互抵消。

  • 判断 $a$ 和 $b$ 能否用完，用不完也是不行的。

  • 开 long long

  • $a$ 和 $b$ 要均衡使用（尽量使 $a$ 和 $b$ 相等）

代码

#include<bits\/stdc++.h>
#define ll long long
#define int long long
#define int_128 __int128
#define lowbit(x) (x&(-x))
using namespace std;
int a,b,c;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b>>c;
	int cnt=0;
	int x=c;
	while(x) {
		x-=lowbit(x);
		cnt++;
	}
	if(a+b<cnt || (a+b-cnt)%2==1) {
		cout<<-1;
	}
	else {
		int ans=0,anss=0;
		for(int i=0;i<=60;i++){
			if(c&(1ll<<i)){
				if(a>=b){
					ans|=(1ll<<i);
					a--;
				}
				else {
					anss|=(1ll<<i);
					b--;
				}
			}
		}
		for(int i=0;i<=60;i++){
			if((c&(1ll<<i)) == 0){
				if(a&&b){
					a--;
					b--;
					ans|=(1ll<<i);
					anss|=(1ll<<i);
				}
				else {
					break;
				}
			}
		}
		if(a||b){
			cout<<-1;
		}
		else cout<<ans<<" "<<anss<<"\n";
	}
	return 0;
}

题解：P10679 『STA - R6』spec

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-30 19:59:22

极限AC

赛事想出了一个很极限的算法，复杂度十分抽象，只能说拜谢洛谷评测机。

思路

很显然当 $α$ 是 $1$ 的时候，肯定可以得到所有的 $x_i$ ，所以答案肯定大于等于 $1$ 。之后我们通过一点点的思考可以知道，如果 $α$ 比 $x_1$ 大 $1$ 以上的话，一定是不能够得到 $x_1$ 的，所以我们可以求出枚举的范围。之后我们在这个区间上枚举，每 $0.000002$ 枚举一次，并进行检查，就能找到最大的 $α$ 。

CODE

#include<bits\/stdc++.h>
#define double long double
using namespace std;
int n,a[100005];

set<int> ss;
bool check(double x){
    for(int i=1;i<=n;i++){
    	int l=0,r=1e4,flag=0;
    	int ans=1e9;
    	while(l<=r){
    		int mid=(l+r)>>1;
    		if((int)ceil(mid*x)-1<=a[i]){
    			l=mid+1;
			}
			else {
				r=mid-1;
				ans=min(ans,mid);	
			}
		}
		for(int j=ans-2;j<=ans+2;j++){
			if((int)ceil(j*x)-1==a[i]){
				flag=1;
				break;
			}
		}
		if(flag==0) return 0;
	}
	return 1;
}
double ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
    	int x;
    	cin>>x;
    	ss.insert(x);
	}
	n=0;
    for(auto i:ss){
    	a[++n]=i;
	}
    for(double i=a[1]+1;i>=1;i-=0.000002){
        if(check(i)){
            cout<<fixed<<setprecision(7)<<i;
            return 0;
        }
    }
    return 0;
}

ABC365_G

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-04 08:43:41

题目链接

abc365_g

思路

类似于扫描线，只不过不需要用线段树，因为每次只用查询两个人，所以直接模拟两个人进出房间的状态和进出的时间。

实现

用 $vector$ 存下所有人各自的操作，对于每一次询问直接暴力找时间最早的未完成操作，更改标记，计算同时在场的时间即。加上记忆化，防止反复询问同一组人。

代码

#include<bits\/stdc++.h>
#define int long long
using namespace std;
int n,m,q;
vector<int> v[200005];
unordered_map<int,int> mp[200005],vis[200005];
\/\/用unordered_map会更快
int ask(int x,int y){
	if(vis[x][y]==1) return mp[x][y];\/\/记忆化
	int sum=0,i=0,j=0,flag=0,flagg=0,pos=0;
	while(i!=v[x].size()&&j!=v[y].size()){\/\/两人都没有操作结束
		\/\/根据扫描线思路，优先操作时间更早的
		if(v[x][i]<v[y][j]){
			if(flag==1){
				if(flagg==1) sum+=v[x][i]-pos;
				pos=v[x][i];
				flag=0;
			}
			else {
				flag=1;
				pos=v[x][i];
			}i++;
		}
		else {
			if(flagg==1){
				if(flag==1) sum+=v[y][j]-pos;
				pos=v[y][j];
				flagg=0;
			}
			else  {
				flagg=1;
				pos=v[y][j];
			}j++;
		}
	}
	mp[x][y]=sum;
	vis[x][y]=1;
	\/\/不要直接把mp当成标记，如果两人没有同时出现的话，会被当成没有计算过，导致记忆化无效
	
	return sum;
}
signed main(){
 	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 	\/\/cin与cout优化
	cin>>n>>m;
	for(int i=1,t,x;i<=m;i++){
		cin>>t>>x;
		v[x].emplace_back(t);
		\/\/据说emplace比push快
	} 
	cin>>q;
	for(int i=1,x,y;i<=q;i++){;
		cin>>x>>y;
		cout<<ask(x,y)<<"\n";
	} 
    return 0;
}

4656ms 的代码

关于时间复杂度

应该是 $O(q\sqrt m)$ 。

考虑卡这份代码，应该使 $\sqrt m$ 人的进出次数都为 $\sqrt m$ 次，考虑每一次都是不同的两个人（使记忆化不生效），这样每一次查询是 $(\sqrt m +\sqrt m)$ 次操作。具体我也不会证明，感性理解一下。

警示后人

给室友卡了一晚上常，不要忘了优化一下常数。

共 40 篇博客
中文 English

鲁ICP备2025150228号

服务器时间: 2025-12-20 10:18:34 | 开源项目