20240716 Codeforces题目

A - Split the Multiset

题目

多集是一组数字，其中可以有相等的元素，数字的顺序无关紧要。例如， { 2 , 2 , 4 } \{2,2,4\} {2,2,4} 是一个multiset。

你有一个多集 $S$ 。最初，multiset只包含一个正整数 $n$ 。即 S = { n } S=\{n\} S={n} 。另外，还有一个给定的正整数 $k$ 。

在一次操作中，您可以选择 $S$ 中的任意正整数 $u$ ，并从 $S$ 中删除一个 $u$ 的副本。然后，在 $S$ 中插入不超过 $k$ 个正整数，使所有插入的整数之和等于 $u$ 。

找出使 $S$ 包含 $n$ 的最小操作次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1\le t\le 1000$ )。下面是测试用例的描述。

每个测试用例的唯一一行包含两个整数 $n,k$ ( $1\le n\le 1000,2\le k\le 1000$ )。

输出

对于每个测试用例，打印一个整数，这是所需的答案。

AC代码

#include
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define PII pair<int,int>
void solve()
{
	int n,k;cin>>n>>k;
    if(n==1)cout<<"0\n";
    else
    {
        int ans=0;
        while(n>k)
        {
            ans++;
            n=n-k+1;//每次消除k-1
        }
        cout<<ans+1<<'\n';
    }
}
signed main()
{
	IOS
	int t;cin>>t;
	while(t--)solve();
	return 0;
}

B. Make Majority

题目

给定一个序列 $[a_1,\dots ,a_n]$ ，其中每个元素 $a_i$ 要么是 $0$ ，要么是 $1$ 。您可以对序列应用多个(可能为零)操作。在每个操作中，您选择两个整数 $1\le l\le r\le |a|$ (其中 $|a|$ 是 $a$ 的当前长度)并将 $[a_l,\dots ,a_r]$ 替换为单个元素 $x$ ，其中 $x$ 是 $[a_l,\dots ,a_r]$ 的大部分。

这里，由 $0$ 和 $1$ 组成的序列的大部分定义如下:假设序列中分别有 $c_0$ 个零和 $c_1$ 个1。

—如果为 $c_0\ge c_1$ ，则多数为 $0$ 。
— $c_{0}lt;c_1$ ，多数为 $1$ 。

例如，假设 $a=[1,0,0,0,1,1]$ 。如果我们选择 $l=1,r=2$ ，结果序列将是 $[0,0,0,1,1]$ 。如果我们选择 $l=4,r=6$ ，结果序列将是 $[1,0,0,1]$ 。

确定是否可以通过有限的操作生成 $a=[1]$ 。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1\le t\le 4\cdot 10^4$ )。下面是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ( $1\le n\le 2\cdot 10^5$ )。

每个测试用例的第二行包含一个由 $0$ 和 $1$ 组成的字符串，描述序列 $a$ 。

可以保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$ 。

输出

对于每个测试用例，如果可以生成 $a=[1]$ ，则打印YES。否则，打印NO。您可以在任何情况下输出答案(上或下)。例如，字符串yEs、yEs、yEs和yEs将被识别为积极响应。

AC代码

#include
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define PII pair<int,int>
string s,t;
void solve()
{
    int n;cin>>n;
	s.clear();cin>>s;
    t.clear();
    int a=0,b=0;
    for(int i=0;i<n;)
    {
        if(s[i]=='1')
        {
            t+=s[i];
            a++;//一个‘1’为一个‘1’
            i++;
        }
        else
        {
            b++;
            t+='0';
            while(i<n&&s[i]=='0')i++;//一段连续的‘0’为1个零
        }
    }
    if(a>b)cout<<"YES\n";
    else cout<<"NO\n";
}
signed main()
{
	IOS
	int t;cin>>t;
	while(t--)solve();
	return 0;
}

C. Increasing Sequence with Fixed OR

题目

您将得到一个正整数 $n$ 。找出满足下列条件的最长正整数序列 $a=[a_1,a_2,\dots ,a_k]$ ，并输出该序列:

-所有 $1\le i\le k$ 的 $a_i\le n$ 。
— $a$ 严格递增。即所有 $2\le i\le k$ 都为 KaTeX parse error: Expected 'EOF', got '&' at position 4: a_i&̲gt;a_{i-1} 。
—所有 $2\le i\le k$ 对应 $a_i|a_{i-1}=n$ ，其中 $|$ 表示位或操作。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1\le t\le 1000$ )。下面是测试用例的描述。

每个测试用例的唯一一行包含一个整数 $n$ ( $1\le n\le 10^{18}$ )。

它保证最长有效序列的长度总和不超过 $5\cdot 10^5$ 。

输出

对于每个测试用例，打印两行。在第一行中，打印构造序列 $k$ 的长度。在第二行，打印 $k$ 正整数，表示序列。如果有多个最长序列，则可以打印其中任何一个。

AC代码

#include
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
int popcount(int x)
{
	if(!x)return 0;// 如果 x 等于 0，则直接返回 0，因为二进制中没有任何位为 1。
	int i=0;
	while((x>>i & 1)==0)++i; // 从低位开始检查 x 的二进制表示，找到第一个为 1 的位。
	return pow(2,i);// 返回一个值，该值是 2 的 i 次幂，即返回第一个为 1 的位所在的位数的幂次方。
}
void solve()
{
    int n;cin>>n;
    vector<int>ans={n};
    int nn=n;
    while(nn)
    {
        int t=popcount(nn);// 2 的第一个 1 的位数幂
        nn-=t;
        if(n-t)ans.push_back(n-t);
    }
    cout<<ans.size()<<'\n';
    sort(ans.begin(),ans.end());
    for(auto x : ans)cout<<x<<' ';
    cout<<'\n';
}
signed main()
{
    int t;cin>>t;
    while(t--)solve();
    return 0;
}