比赛链接
A 小红出题
题目描述
小红每周一到周五上班,工作日每天都要出 道题目。
已知小红入职当天为星期一,并且已经在职 天。
请问她总共出了几道题目?
第一行有一个整数 。
题解
算出经历了多少个完整的星期。然后算出剩下多少天,进行相加。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve()
{
int n;
cin>>n;
int x=n/7;
int ans=x*15;
n%=7;
if(n>=5) n=5;
ans+=n*3;
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
}
n=int(input())
x=n//7
ans=x*15
n%=7
if n>=5: n=5
ans+=n*3
print(ans)
B 串串香
题目描述
给定一个长度为 ,仅包含小写字母的字符串
。
请你构造出一个非空字符串
,使得它在
中作为子串出现的次数最多。
子串是指,从原字符串中连续截取一些字符,得到的新字符串。
第一行有一个整数
。
第二行有一个字符串 ,字符串仅包含小写字母。
题解
出现次数最多的字符串一定可以用单个字母表示,因为假设为所求答案,那么
出现的次数一定会大于等于
的次数(会有零散的
)。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
map<char,int> mp;
for(int i=0;i<n;i++){
mp[s[i]]++;
}
char a;
int maxx=0;
for(auto i:mp){
if(i.second>maxx){
maxx=i.second;
a=i.first;
}
}
cout<<a<<endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
}
n=int(input())
s=input()
mp={}
for i in range(n):
mp[s[i]]=mp.get(s[i],0)+1
a=''
maxx=0
for k,v in mp.items():
if v>maxx:
maxx=v
a=k
print(a)
C 小红的gcd
题目描述
小红有一个长度为 的数组,她希望数组元素之和越少越好。
她可以进行任意次操作,每次选择数组中的两个元素 和
,令
。
所有操作结束后,请你输出最小的数组元素之和。
第一行有一个整数 。
第二行有 个整数
。
题解
对俩个数进行操作后,结果是小于等于之前的俩个数的。且可以无限次的操作。那么最终答案一定是对所有数俩俩进行一次操作。最后所有数都会变为
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+10;
int a[N];
void solve()
{
int n;
cin>>n;
int f;
cin>>f;
for(int i=2;i<=n;i++){
cin>>a[i];
f=__gcd(a[i],f);
}
cout<<n*f<<endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
}
import math
n=int(input())
f=int(input())
a=[0]*(n+1)
for i in range(2,n+1):
a[i]=int(input())
f=math.gcd(a[i],f)
print(n*f)
D 奇偶调整
题目描述
小红有一个长度为 的数组
,第
个元素为
。
小红可以执行两种操作,操作内容如下:
1.选择一个偶数元素 ,令
。
2.选择一个奇数元素 ,令
。
其中,操作 最多执行
次,操作
最多执行
次。
小红想最小化数组元素之和,请你输出这个值。
代表按位异或。
第一行有三个整数
,
和
。
第二行有 个整数
。
题解
操作1即为将一个偶数除二,操作二为将一个奇数减一。所以贪心的想,每次对最大的数进行操作,如果为奇数,操作1,2都有次数,则可以让他减一变为偶数后进行操作1。如果为偶数,则进行操作2。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+10;
int aa[N];
void solve()
{
int n,m,k;
cin>>n>>m>>k;
priority_queue<int> q;
for(int i=1;i<=n;i++){
int x;
cin>>x;
q.push(x);
}
int ans=0;
while(q.size()){
int t=q.top();
q.pop();
int tt=t;
if(t%2){
if(k && m){
t-=1;
t/=2;
k--;
m--;
}else if(k){
t-=1;
k--;
}
}else{
if(m){
t/=2;
m--;
}
}
if(t==tt){
ans+=t;
}else{
q.push(t);
}
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
}
import heapq
n,m,k=map(int,input().split())
q=[]
for _ in range(n):
x=int(input())
heapq.heappush(q, -x)
ans=0
while q:
t=-q[0]
heapq.heappop(q)
tt=t
if t%2:
if k and m:
t-=1
t//=2
k-=1
m-=1
elif k:
t-=1
k-=1
else:
if m:
t//=2
m-=1
if t==tt:
ans+=t
else:
heapq.heappush(q, -t)
print(ans)
E 幂次进近
题目描述
给定 次询问,每次询问给出两个正整数
和
。
请你找到最小的正整数 ,使得
的绝对值最小。
第一行有一个整数
。
随后 行,每行两个整数
。
题解
先进行特判,若k超过了60,直接输出1,因为进行二分查找,找到最大的
使满足
大于等于
。再将
与
计算的结果进行比较,取较小的。本题需要注意的是由于n,k都比较大,需要使用__int128。
本题和cf一场div4的E题比较像:相似题目推荐
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define lll __int128
int n,k;
lll qmi(lll a,lll b)
{
lll ans=1;
while(b){
if(b&1) ans=ans*a;
b>>=1;
a=a*a;
}
return ans;
}
bool check(lll x){
lll ans=1;
for(int i=1;i<=k;i++){
ans*=x;
if(ans/n>=1) return 0;
}
return 1;
}
void solve()
{
cin>>n>>k;
if(k>60){
cout<<1<<endl;
return;
}
if(k==1){
cout<<n<<endl;
return;
}
lll l=1,r=n;
while(l<r){
lll mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
int ans=l;
if(n-qmi(l,k)<qmi(l+1,k)-n) cout<<ans<<endl;
else cout<<ans+1<<endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) solve();
}
def qmi(a,b):
ans=1
while b:
if b&1: ans*=a
b>>=1
a*=a
return ans
def check(x):
ans=1
for i in range(1,k+1):
ans*=x
if ans//n>=1: return False
return True
n,k=map(int,input().split())
if k>60:
print(1)
else:
if k==1:
print(n)
else:
l,r=1,n
while l<r:
mid=(l+r+1)>>1
if check(mid): l=mid
else: r=mid-1
ans=l
if n-qmi(l,k)<qmi(l+1,k)-n: print(ans)
else: print(ans+1)
F 同位序列
题目描述
定义 为
在二进制表示下的
的个数。
例如 ,
,
。
定义 为 第一个比
大的数字
,使得
。
例如 ,
,
。
给你一个长度为 的数组
,第
个元素为
。
我们希望从数组 中挑选出一些元素,构造一个长度为
的同位序列
。
同位序列 满足如下条件:
对于所有的 ,都有
。
当然,同位序列越长越好,请你最大化其长度 ,然后输出
和对应的同位序列。
如果有多解,输出任意一个即可。
第一行有一个整数 。
第二行有 个整数
。
题解
先处理出每个数的给 。然后用map处理最长长度。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define lll __int128
const int N=1e5+10,M=32;
int a[N];
void solve()
{
int n;
cin>>n;
map<int,int> g;
for(int i=1;i<=n;i++){
cin>>a[i];
vector<int> bit(M);
for(int j=0;j<M;j++){
if(a[i]>>j&1) bit[M-j-1]=1;
}
next_permutation(bit.begin(),bit.end());
for(int j=0;j<M;j++){
if(bit[M-j-1]) g[a[i]]|=1<<j;
}
}
map<int,int> mp;
int maxx=0,id=0;
sort(a+1,a+1+n,greater<int>());
for(int i=1;i<=n;i++){
if(mp[g[a[i]]]) mp[a[i]]=mp[g[a[i]]]+1;
else mp[a[i]]=1;
if(mp[a[i]]>maxx){
maxx=mp[a[i]];
id=a[i];
}
}
vector<int> ans;
ans.push_back(id);
while(mp[g[id]]){
id=g[id];
ans.push_back(id);
}
cout<<ans.size()<<endl;
for(auto i:ans){
cout<<i<<" ";
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
}
from itertools import permutations
n=int(input())
a=[0]*(n+1)
g={}
for i in range(1,n+1):
a[i]=int(input())
bit=[0]*32
for j in range(32):
if a[i]>>j&1: bit[31-j]=1
for bit_permutation in permutations(bit):
for j in range(32):
if bit_permutation[31-j]: g[a[i]]|=1<<j
mp={}
maxx=0
id=0
a.sort(reverse=True)
for i in range(1,n+1):
if g[a[i]] in mp: mp[a[i]]=mp[g[a[i]]]+1
else: mp[a[i]]=1
if mp[a[i]]>maxx:
maxx=mp[a[i]]
id=a[i]
ans=[id]
while g.get(id):
id=g[id]
ans.append(id)
print(len(ans))
print(*ans)