塘厦仿做网站,泗县住房和城乡建设局网站,娱乐游戏网站建设,wordpress图集主题A - Split the Multiset
题目
多集是一组数字#xff0c;其中可以有相等的元素#xff0c;数字的顺序无关紧要。例如#xff0c; { 2 , 2 , 4 } \{2,2,4\} {2,2,4} 是一个multiset。
你有一个多集 S S S 。最初#xff0c;multiset只包含一个正整数 n n n 。即 S {…A - Split the Multiset
题目
多集是一组数字其中可以有相等的元素数字的顺序无关紧要。例如 { 2 , 2 , 4 } \{2,2,4\} {2,2,4} 是一个multiset。
你有一个多集 S S S 。最初multiset只包含一个正整数 n n n 。即 S { n } S\{n\} S{n} 。另外还有一个给定的正整数 k k k 。
在一次操作中您可以选择 S S S 中的任意正整数 u u u 并从 S S S 中删除一个 u u u 的副本。然后在 S S S 中插入不超过 k k k 个正整数使所有插入的整数之和等于 u u u 。
找出使 S S S 包含 n n n 的最小操作次数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 t t t ( 1 ≤ t ≤ 1000 1 \le t \le 1000 1≤t≤1000 )。下面是测试用例的描述。
每个测试用例的唯一一行包含两个整数 n , k n,k n,k ( 1 ≤ n ≤ 1000 , 2 ≤ k ≤ 1000 1\le n\le 1000,2\le k\le 1000 1≤n≤1000,2≤k≤1000 )。
输出
对于每个测试用例打印一个整数这是所需的答案。
AC代码
#includebits/stdc.h
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 pairint,int
void solve()
{int n,k;cinnk;if(n1)cout0\n;else{int ans0;while(nk){ans;nn-k1;//每次消除k-1}coutans1\n;}
}
signed main()
{IOSint t;cint;while(t--)solve();return 0;
}B. Make Majority
题目
给定一个序列 [ a 1 , … , a n ] [a_1,\ldots,a_n] [a1,…,an] 其中每个元素 a i a_i ai 要么是 0 0 0 要么是 1 1 1 。您可以对序列应用多个(可能为零)操作。在每个操作中您选择两个整数 1 ≤ l ≤ r ≤ ∣ a ∣ 1\le l\le r\le |a| 1≤l≤r≤∣a∣ (其中 ∣ a ∣ |a| ∣a∣ 是 a a a 的当前长度)并将 [ a l , … , a r ] [a_l,\ldots,a_r] [al,…,ar] 替换为单个元素 x x x 其中 x x x 是 [ a l , … , a r ] [a_l,\ldots,a_r] [al,…,ar] 的大部分。
这里由 0 0 0 和 1 1 1 组成的序列的大部分定义如下:假设序列中分别有 c 0 c_0 c0 个零和 c 1 c_1 c1 个1。
—如果为 c 0 ≥ c 1 c_0\ge c_1 c0≥c1 则多数为 0 0 0 。 — c 0 l t ; c 1 c_0lt;c_1 c0lt;c1 多数为 1 1 1 。
例如假设 a [ 1 , 0 , 0 , 0 , 1 , 1 ] a[1,0,0,0,1,1] a[1,0,0,0,1,1] 。如果我们选择 l 1 , r 2 l1,r2 l1,r2 结果序列将是 [ 0 , 0 , 0 , 1 , 1 ] [0,0,0,1,1] [0,0,0,1,1] 。如果我们选择 l 4 , r 6 l4,r6 l4,r6 结果序列将是 [ 1 , 0 , 0 , 1 ] [1,0,0,1] [1,0,0,1] 。
确定是否可以通过有限的操作生成 a [ 1 ] a[1] a[1] 。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 t t t ( 1 ≤ t ≤ 4 ⋅ 1 0 4 1 \le t \le 4\cdot 10^4 1≤t≤4⋅104 )。下面是测试用例的描述。
每个测试用例的第一行包含一个整数 n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1\le n\le 2\cdot 10^5 1≤n≤2⋅105 )。
每个测试用例的第二行包含一个由 0 0 0 和 1 1 1 组成的字符串描述序列 a a a 。
可以保证所有测试用例的 n n n 之和不超过 2 ⋅ 1 0 5 2\cdot 10^5 2⋅105 。
输出
对于每个测试用例如果可以生成 a [ 1 ] a[1] a[1] 则打印YES。否则打印NO。您可以在任何情况下输出答案(上或下)。例如字符串yEs、yEs、yEs和yEs将被识别为积极响应。
AC代码
#includebits/stdc.h
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 pairint,int
string s,t;
void solve()
{int n;cinn;s.clear();cins;t.clear();int a0,b0;for(int i0;in;){if(s[i]1){ts[i];a;//一个‘1’为一个‘1’i;}else{b;t0;while(ins[i]0)i;//一段连续的‘0’为1个零}}if(ab)coutYES\n;else coutNO\n;
}
signed main()
{IOSint t;cint;while(t--)solve();return 0;
}C. Increasing Sequence with Fixed OR
题目
您将得到一个正整数 n n n 。找出满足下列条件的最长正整数序列 a [ a 1 , a 2 , … , a k ] a[a_1,a_2,\ldots,a_k] a[a1,a2,…,ak] 并输出该序列:
-所有 1 ≤ i ≤ k 1\le i\le k 1≤i≤k 的 a i ≤ n a_i\le n ai≤n 。 — a a a 严格递增。即所有 2 ≤ i ≤ k 2\le i\le k 2≤i≤k 都为 KaTeX parse error: Expected EOF, got at position 4: a_i̲gt;a_{i-1} 。 —所有 2 ≤ i ≤ k 2\le i\le k 2≤i≤k 对应 a i ∣ a i − 1 n a_i\,|\,a_{i-1}n ai∣ai−1n 其中 ∣ | ∣ 表示位或操作。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 t t t ( 1 ≤ t ≤ 1000 1 \le t \le 1000 1≤t≤1000 )。下面是测试用例的描述。
每个测试用例的唯一一行包含一个整数 n n n ( 1 ≤ n ≤ 1 0 18 1\le n\le 10^{18} 1≤n≤1018 )。
它保证最长有效序列的长度总和不超过 5 ⋅ 1 0 5 5\cdot 10^5 5⋅105 。
输出
对于每个测试用例打印两行。在第一行中打印构造序列 k k k 的长度。在第二行打印 k k k 正整数表示序列。如果有多个最长序列则可以打印其中任何一个。
AC代码
#includebits/stdc.h
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 i0;while((xi 1)0)i; // 从低位开始检查 x 的二进制表示找到第一个为 1 的位。return pow(2,i);// 返回一个值该值是 2 的 i 次幂即返回第一个为 1 的位所在的位数的幂次方。
}
void solve()
{int n;cinn;vectorintans{n};int nnn;while(nn){int tpopcount(nn);// 2 的第一个 1 的位数幂nn-t;if(n-t)ans.push_back(n-t);}coutans.size()\n;sort(ans.begin(),ans.end());for(auto x : ans)coutx ;cout\n;
}
signed main()
{int t;cint;while(t--)solve();return 0;
}
