首页 > 其他分享 >CodeTON Round 9 (Div. 1 + Div. 2)

CodeTON Round 9 (Div. 1 + Div. 2)

时间:2024-11-25 16:44:31浏览次数:9  
标签:le int ll CodeTON long oplus Div include Round

CodeTON Round 9 (Div. 1 + Div. 2) 总结

A

自己推一下就能出来的,输出奇数即可。

因为要递增,所以尽可能取小的数字。

  • \(i=1\),余数肯定是 \(0\),尽可能小,所以 \(a_1=1\)。
  • \(i=2\),余数尽可能小且不重,是 \(1\),所以 \(a_1=1+2=3\)
  • \(i=3\),余数为 \(2\),\(a_3=2+3=5\)。

这样推导后知道 \(a_i=2 \times i+1\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=55;
int n;
void solve()
{
    cin>>n;
	for(int i=1;i<=n;i++) cout<<i*2-1<<' ';
    cout<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B

肯定是往数量少的考虑。

\(f(t)\) 为偶数,以 \(t\) 的大小为依据分类讨论。设 \(\lvert t\rvert\) 为字符串 \(t\) 的大小。

  • \(\lvert t\rvert = 1\),显然只有一个非空子串。
  • \(\lvert t\rvert = 2\)。
    • 当两个字符不同时,一定有三个子串,不符。
    • 当两个字符相同时,会有两个不同的子串,符合题意。
  • \(\lvert t\rvert = 3\)。只有三个字符都不同时,才会有 \(6\) 个不同的子串。

所以就是找连续的三个不同的字符或者两个相同的字符。这样思考一下,只有出现类似于 ababababa 这样的字符才没有子串符合条件。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1e5+5;
string s;
void solve()
{
    cin>>s;
    int n=s.size();
    for(int i=0;i<n-2;i++)
        if(s[i]!=s[i+1]&&s[i]!=s[i+2]&&s[i+1]!=s[i+2])
        {
            cout<<s[i]<<s[i+1]<<s[i+2]<<'\n';
            return ;
        }
    for(int i=0;i<n-1;i++) 
        if(s[i]==s[i+1])
        {
            cout<<s[i]<<s[i+1]<<'\n';
            return ;
        }
    cout<<-1<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C1

C 题都用到了一个性质,按位异或可以看作是不进位的加法。设 \(y>x\),就有 \(y \oplus x \in [y-x,y+x]\)。

因此当 \(y>2x\) 时,\(y \oplus x > x\),因此 \(y \oplus x\) 不可能是 \(x\) 的因数。
\(y>2x\),也有 \(x < \frac{y}{2}\),\(y \oplus x > \frac{y}{2}\),又因为 \(x \ge 1\),所以 \(y \oplus x \neq y\) ,所以也不可能是 \(y\) 的因数。

所以 \(y \in [1,\min(2x,m)]\) 时才会产生贡献。暴力枚举判断即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1;
int x;
ll m;
void solve()
{
    cin>>x>>m;
    ll n=1,cnt=0;
    while(n<=x) n<<=1;
    for(int y=1;y<=min(n-1,m);y++) 
    {
        int t=x^y;
        if(t==0) continue;
        if(x%t==0||y%t==0) cnt++;
    }
    cout<<cnt<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C2

可以先打表找规律,发现小于 \(m\) 的几乎所有 \(x\) 的倍数都满足。

设 \(t=x \oplus y\),先考虑,\(t\) 为 \(y\) 的倍数。
按位异或可以看作是不进位的加法,所以当 \(x<y\) 时,\(t<y+x=2y\),而因为 \(x \ge 1\),\(t \neq y\),\(y\) 的最小倍数为 \(2y\)。所有当 \(x<y\) 时,\(t\) 不可能是 \(y\) 的倍数。
所以只考虑 \(y \le x\),\(x\) 较小,暴力枚举 \(y\) 判断即可。

再考虑 \(t\) 是 \(x\) 的倍数。\(y=x\oplus t\),因为 \(x \oplus t \le x+t\),所以 \(x+t \le m\) 时,\(y \le m\)。所以 \(t \le m-x\) 且 \(t\) 为 \(x\) 的倍数时都符合题意。但要注意当 \(t=x\) 时,\(y=0\),该情况要舍去。还有因为 \(t=0\) 时,\(y=x\),这种情况会在考虑 \(t\) 为 \(y\) 的倍数被计算,所有也没有必要重复算。

\(t \oplus x \ge t-x\),若 \(t-x>m\),则有 \(y=t \oplus x>m\),不符。所以 \(t>m+x\) 时没有贡献。

还剩下一段区间为 \([m-x,m+x)\),最多产生两个 \(x\) 的倍数,判断一下 \(y\) 是否大于 \(x\) 且小于等于 \(m\) 即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1;
ll x,m;

void solve()
{
    cin>>x>>m;
    ll ans=0,t;
	if(m>x)
	{
		ans+=max((m-x)/x-1,0ll);
		t=m/x*x;
		ll y=x^t;
		if(y>x&&y<=m) ans++;
		t+=x,y=x^t;
		if(y>x&&y<=m) ans++;
	}
    for(int y=1;y<=min(x,m);y++)
    {
        t=x^y;
        if(t%y==0) ans++;
    }
    cout<<ans<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

D

感觉上比 C2 简单。

先转变下条件,若 \(\gcd(i,j)=i\),即 \(i\) 是 \(j\) 的因数,式子就变为 \(a_i \neq \gcd(a_i,a_j),1\le i < j \le n\),其中 \(j\) 为 \(i\) 的倍数。

开始构造,将 \(s\) 从大到小排序。

  • \(i=1\),所以 \(2 \le j \le n\) 的所有 \(j\) 都有 \(a_i \neq \gcd(a_i,a_j)\),所以不妨让 \(a_1\) 为最大,为 \(s_1\)。然后 \(2 \le j \le n\) 的所有 \(a_j\) 都不能是 \(s_1\)。
  • \(i=2\),确定为 \(s_2\),能影响到 \(a_4,a_6,a_8,\dots\),这些都不能是 \(s_2\)。
  • \(i=3\),可以为 \(s_2\),影响到 \(a_6,a_9,a_12,\dots\),这些不能是 \(s_2\)。
  • \(a_4\) 可以为 \(s_3\),\(a_5\) 可以为 \(s_2\),\(a_6\) 可以为 \(s_3\)。

就这么推下去,找到 \(a_i\) 可以取的最大的 \(s_j\)。若超出 \(m\),就肯定无解。

枚举次数为 \(\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\dots+\frac{n}{n} \approx n\log(n)\),所以时间复杂度为 \(O(n\log(n))\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m;
int s[N],a[N];
bool cmp(int x,int y)
{
	return x>y;
}
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>s[i];
	sort(s+1,s+m+1,cmp);
	for(int i=1;i<=n;i++) a[i]=0;
	a[1]=1;
	int mx=0;
	for(int i=1;i<=n;i++)
		for(int j=i*2;j<=n;j+=i)
		{
			a[j]=max(a[j],a[i]+1);
			mx=max(mx,a[j]);
		}
	if(mx>m)
	{
		cout<<-1<<'\n';
		return ;
	}
	for(int i=1;i<=n;i++) cout<<s[a[i]]<<' ';
	cout<<'\n';
}
int main ()
{
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

标签:le,int,ll,CodeTON,long,oplus,Div,include,Round
From: https://www.cnblogs.com/zhouruoheng/p/18565079

相关文章

  • 【牛客训练记录】牛客周赛 Round 69
    训练情况赛后反思好吧,D题没想到二进制枚举,以为\(O(2^knm)\)不可做。。。A题要求要等差数列,我们先求公差,为两元素的最大值-最小值,再在最大值的基础上加上公差即可。#include<bits/stdc++.h>//#defineintlonglong#defineendl'\n'usingnamespacestd;voidsol......
  • 【MX-S7】梦熊 NOIP 2024 模拟赛 3 & SMOI Round 2
    俩签到俩不可做是吧。Rank【MX-S7-T1】「SMOI-R2」HappyCard签到题一号,以为撑死评个黄但没想到那么多人不会打扑克。考虑炸弹也是三带一,出三带一肯定更优秀。考虑将所有牌变为若干个三张和剩余的,那么三张先带单张,再将对子拆开带。那么现在就有以下几种情况:单张太多,那么......
  • 牛客周赛 Round 69(A~E)
    https://ac.nowcoder.com/acm/contest/96115#question真难过,一个小时竟然做不出F。没想到F是线段树的变式,我还想开7,8个树状数组进行维护,直接秀逗了。要做大物作业,先丢个题解吧A.构造C的歪#include<iostream>#include<queue>#include<map>#include<set>#include<vector>#in......
  • 【MX-S7】梦熊 NOIP 2024 模拟赛 3 & SMOI Round 2(同步赛)
    【MX-S7】梦熊NOIP2024模拟赛3&SMOIRound2(同步赛)\(T1\)luoguP11323【MX-S7-T1】「SMOI-R2」HappyCard\(20pts\)发现可以把「炸弹」也看做「三带一」。先使用「三带一」带走原用于出「单牌」的牌,若「三带一」还有剩余则尝试带走原用于出「对子」的牌,否则直接......
  • CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)(A - D) (C2 还在补)
    CodeTONRound9(Div.1+Div.2,Rated,Prizes!)4/11(ABC1D)A.ShohagLovesMod题目大意Shohag有一个整数nn。请帮助他找到一个递增的整数序列1≤a1<a2<…<an≤1001≤a1<a2<…<an≤100,使得对于所有的1≤i<j≤n1≤i<j≤n,都满足aimodi≠ajmodjaimodi≠ajmodj∗∗......
  • [CSS] Houdini CSS to animate linear gradient background
    https://developer.mozilla.org/en-US/docs/Web/API/Houdini_APIs<!doctypehtml><htmllang="en"><head><metacharset="utf-8"/><title>Houdini</title><linkrel="stylesheet"......
  • 如何让大小不同的图片等比缩放不变形显示在固定大小的div里?写个例子
    要让大小不同的图片等比缩放不变形显示在固定大小的div里,关键在于设置object-fitCSS属性。以下是一个例子,并解释了不同的object-fit值的效果:<!DOCTYPEhtml><html><head><title>ImageScaling</title><style>.container{width:200px;height:200px;border......
  • 写出div在不固定高度的情况下水平垂直居中的方法?
    在div高度不固定的情况下,实现水平垂直居中的方法有很多,以下是几种常见且有效的方法:1.Flexbox布局(推荐):这是现代CSS中最简洁和灵活的解决方案。.container{display:flex;justify-content:center;/*水平居中*/align-items:center;/*垂直居中*/min......
  • 外层有一个自适应高度的div,里面有两个div,一个高度固定300px,另一个怎么填满剩余的高度?
    YoucanachievethisusingacombinationofCSSFlexboxorGrid.Herearetwosolutions:1.FlexboxSolution:<divclass="outer"><divclass="fixed-height">FixedHeight(300px)</div><divclass="fill-remai......
  • FastHTML 组件:学习使用 Div、P、A、Form 等常用组件
    FastHTML提供了一系列内置组件,用于构建HTML页面。这些组件可以像Python对象一样使用,并可以嵌套使用来创建复杂的页面结构。以下是一些常用的FastHTML组件:Div:创建一个div元素,可以包含其他HTML元素。P:创建一个段落元素,可以包含文本或其他HTML元素。A:创建......