难度预测(从左到右难度升序): easy: F A D easy-mid: E C mid: B I G hard: K H very hard: J
实际难度:I mid->hard。其余和预期相符。
F.迎接终结的寂灭
知识点:无
签到题。输出42即可通过本题。
参考代码(PHP语言):
42
A.不断减损的时间
知识点:贪心
对所有的正整数能操作就操作(显然操作后会变小),而0和负数则不操作。
参考代码:
#include<bits/stdc++.h>
using namespace std;
int a[202020];
int main(){
int n,i,x;
cin>>n;
long long sum=0;
for(i=0;i<n;i++){
cin>>x;
while(x>0&&x%2==0)x/=2;
sum+=x;
}
cout<<sum;
}
D.宿命之间的对决
知识点:博弈
显然1是先手必输。我们证明所有奇数都是先手必输:由于奇数只包含奇数的因子,那么只能取一个奇数变成偶数(或者变成0直接输掉),然后对方就可以直接取1变成奇数,仍然到必输的状态。因此奇数先手必输,偶数先手必胜。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin>>n;
if(n&1)cout<<"yukari";
else cout<<"kou";
}
E.公平守望的灯塔
知识点:计算几何
首先需要知道一个计算几何的常用知识:向量和向量的夹角为90度(因为点乘为0)。 那么我们假设向量为,那么我们从点为起点加上向量得到点,那么的中点即为所求。只需要判一下是否是整数即可。(由于只有求中点时除2,所以只需要判奇偶)。 当然本题还可以通过求中垂线和以为直径的圆的交点来求,不过这个做法码量巨大,不是很推荐。如果比赛中萌新实在想不出第一个做法可以尝试用第二个做法。
参考代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
long long ax,ay,bx,by;
cin>>ax>>ay>>bx>>by;
long long x=bx-ax,y=by-ay;
if(x+y&1)return cout<<"No Answer!",0;
long long cx=ax-y,cy=ay+x;
cout<<(cx+bx>>1)<<" "<<(cy+by>>1)<<'\n';
}
C.忽远忽近的距离
知识点:构造
我们从样例可以发现,[3,4,1,2]是一组合法解,那么可以以此构造出所有形式的情况:[3,4,1,2,7,8,5,6]等。 之后我们可以尝试构造和的情况,发现有[4,5,1,2,3]和[4,5,6,1,2,3],那么可以构造出、、的情况,以上分别对应模4等于1、2、3的情况,加上之前的,那么就覆盖了几乎所有正整数(需要特判和时是无解的)。 例如,我们发现13=4*2+5,那么可以构造成:[3,4,1,2,7,8,5,6,12,13,9,10,11],即13=4+4+5的情况。
参考代码:
#include<bits/stdc++.h>
using namespace std;
void out(int n,int x){
for(int i=n+x/2;i<n+x;i++)cout<<i<<" ";
for(int i=n;i<n+x/2;i++)cout<<i<<" ";
}
int main(){
int n,i=1;
cin>>n;
if(n<4||n==7)return cout<<-1,0;
for(i=1;i<=n-11;i+=4){
out(i,4);
}
if(n-i==10){
out(i,5);
out(i+5,6);
return 0;
}
if(i<=n-7)out(i,4),i+=4;
out(i,n-i+1);
}
B.勉强拼凑的记忆
知识点:二分
显然本题满足可以二分答案,并且在给定了正方形边长时,可以O(1)判定能否拼成。总复杂度为O(logn)。
拼边长为正方形的策略是:先用的矩形(共个),还剩一个边长为的正方形,使用的矩形即可。(可以证明,最终一定是在)之间。
另外,本题需要特判的无解情况。
由于出题人的良心,直接把该情况放进样例里,使大家没有被这个特判wa到死去活来,但却遭到了小沙的反对。某沙语录:
参考代码:
#include<bits/stdc++.h>
using namespace std;
long long bs(long long l,long long r,long long n){
if(l==r)return l;
long long mid=l+r>>1;
long long bc=n/2+n%2;
long long chu=mid/bc,yu=mid%bc;
long long cnt=chu*(mid+yu)+yu;
if(cnt>n)return bs(l,mid,n);
return bs(mid+1,r,n);
}
int main(){
int _;
cin>>_;
while(_--){
long long n;
cin>>n;
if(n==1){cout<<1<<'\n';continue;}
if(n==2){cout<<-1<<'\n';continue;}
cout<<bs(n/2,n,n)-1<<'\n';
}
}
I.灵魂碎片的收集
知识点:数论、构造
注意看输入中隐含的一个提示:若是偶数,保证、中至少有一个是素数。 当是素数时,即可以写成的形式。显然只包含这三个因子,得解。 当是素数时,即可以写成的形式。显然只包含这四个因子,得解。 当是奇数时,根据哥德巴赫猜想的结论,我们可以很容易找到两个素数和满足,由于只包含这四个因子,得解。 需要注意,当时,部分情况需要特判。
参考代码:
#include<bits/stdc++.h>
using namespace std;
int f(long long x){
int i;
for(i=2;i*i<=x;i++){
if(x%i==0)return 0;
}
return 1;
}
int main(){
int _;
cin>>_;
while(_--){
long long n,i;
cin>>n;
if(n&1){
if(n==1)cout<<3<<'\n';
else if(n==5)cout<<-1<<'\n';
else if(n==3)cout<<4<<'\n';
else if(n==7)cout<<8<<'\n';
else{
for(i=3;i<(n-1)/2;i++){
if(f(i)&&f(n-1-i))break;
}
cout<<1ll*i*(n-1-i)<<'\n';
}
}
else{
if(f(n-1))cout<<(n-1)*(n-1)<<'\n';
else if(f(n-3))cout<<2*(n-3)<<'\n';
}
}
}
G.严肃古板的秩序
知识点:枚举/dfs
本题为纯码力题,暴力搜索所有情况即可。可以用三进制状压枚举或者dfs完成本题。 需要注意的两点: 1.算出0或者负数时若下一步是#运算应直接终止。 2.当爆int时,快速幂应将底数取模,指数不应取模。 三进制状压枚举介绍: 我们假设'+'用0数位,'-'用1数位,'#'用2数位,那么由三进制的000……到222……这个三进制数就能表示所有的情况了。对于每种情况进行判断运算式是否合法。
参考代码(状压枚举):
#include<bits/stdc++.h>
using namespace std;
vector<long long>v;
long long ans;
int b[202];
long long power(long long a,long long b,long long mod){
long long res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
int main(){
string s;
cin>>s;
int i,temp=0,j;
for(i=0;i<s.length();i++){
if(s[i]=='?'||s[i]=='=')v.push_back(temp),temp=0;
else temp*=10,temp+=s[i]-'0';
}
ans=temp;
while(!b[v.size()]){
long long temp=v[0];
for(j=1;j<v.size();j++){
if(b[j]==0)temp=temp+v[j];
if(b[j]==1)temp=temp-v[j];
if(b[j]==2){
if(temp<=0){temp=-1;break;}
temp=power(temp%v[j],temp,v[j]);
}
}
if(temp==ans){
cout<<v[0];
for(j=1;j<v.size();j++){
if(b[j]==0)cout<<'+';
if(b[j]==1)cout<<'-';
if(b[j]==2)cout<<'#';
cout<<v[j];
}
cout<<"="<<ans;
break;
}
b[1]++;
for(j=1;j<v.size();j++){
b[j+1]+=b[j]/3;
b[j]%=3;
}
}
if(b[v.size()])cout<<-1;
}
K.永恒守候的爱恋
知识点:数论,数学
前置知识:若的质因数分解形式为,那么的因子数量为。 证明如下,对于每个素因子而言,可以取0个、取1个……取个,共有种取法。根据乘法原理,总方案数为 根据这个性质,我们可以想出这样的策略:首先每个素数第一次出现依次排下来,然后还有次数的素数的第二次依次排下来……以此类推。这样一定是最优的。因为当素数的出现次数从次变成次的时候,带来的贡献为;(之前是乘以,现在是乘以)。所以每次优先选择“目前已选择的出现次数最少的素数”是更优的。 这样当我们选择出现次数为i的素数时,前缀因子数量从此时开始即为一个公比为的等比数列;我们可以通过等比数列求和公式快速算出这一段的和。这样总复杂度即为,其中log是逆元部分的复杂度。
参考代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
ll power(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
ll inv(ll x){
return power(x,mod-2);
}
long long a[202020];
int main(){
int n,i;
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
int j=1;
long long temp=1;
long long s=0;
for(i=1;i<=2e5;i++){
while(j<=n&&a[j]<i)j++;
if(j>n)break;
int cnt=n-j+1;
s+=temp*(power(i+1,n-j+1)*inv(power(i,n-j+1))%mod-1)%mod*i%mod;
temp=temp*power(i+1,n-j+1)%mod*inv(power(i,n-j+1))%mod;
s%=mod;
}
cout<<((s+temp-1)%mod+mod)%mod<<'\n';
}
H.穿越万年的轮回
知识点:动态规划,期望
由于每次三种操作的概率相等,因此最终的期望乘以后等于下面问题的答案:每次操作会将一个串分别用三种操作生成3个串,最终会有个串,求所有串的"red"子串数量之和。
这个问题可以直接用dp求解。 设dp[i][j][k]的含义如下:i代表操作次数,j=k=0代表字符串为空,j=1代表前缀是"red",j=2代表前缀是"edr",k=1代表后缀是"red",k=2代表后缀是"edr"。然后dp数组代表满足上述条件的red子串的数量。这样可以分别根据三种操作进行分类讨论来递推了。
参考代码:
#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
long long power(long long a,long long b){
long long res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
long long inv(int x){
return power(x,mod-2);
}
long long dp[200010][3][3],cnt[201010][3][3]; //cnt代表字符串数量,dp代表red子串数量
int main(){
dp[1][1][1]=1;
cnt[1][0][0]=1;
cnt[1][1][1]=1;
cnt[1][2][2]=1;
int n,i,j,k;
cin>>n;
for(i=2;i<=n;i++){
cnt[i][0][0]+=cnt[i-1][0][0];
cnt[i][1][1]+=cnt[i-1][0][0];
cnt[i][2][2]+=cnt[i-1][0][0];
for(j=1;j<=2;j++){
cnt[i][j][1]+=cnt[i-1][j][1]*2+cnt[i-1][j][0]+cnt[i-1][j][2];
cnt[i][j][2]+=cnt[i-1][j][2]*2+cnt[i-1][j][0]+cnt[i-1][j][1];
cnt[i][j][0]+=cnt[i-1][j][0];
dp[i][j][1]+=dp[i-1][j][1]+cnt[i-1][j][1]+dp[i-1][j][0]+cnt[i-1][j][0]+dp[i-1][j][2]+cnt[i-1][j][2];
dp[i][j][2]+= dp[i-1][j][1]+dp[i-1][j][0]+dp[i-1][j][2]+cnt[i-1][j][2];
dp[i][j][1]+=dp[i-1][j][1]*10;
dp[i][j][2]+=dp[i-1][j][2]*10;
dp[i][j][0]+=dp[i-1][j][0]*10;
for(k=0;k<3;k++)dp[i][j][k]%=mod,cnt[i][j][k]%=mod;
}
dp[i][1][1]+=cnt[i-1][0][0];
dp[i][2][2]+=cnt[i-1][2][2]*9;
dp[i][1][1]%=mod;
dp[i][2][2]%=mod;
}
long long res=0;
for(i=0;i<3;i++){
for(j=0;j<3;j++){
res+=dp[n][i][j];
}
}
cout<<res%mod*power(inv(3),n)%mod;
}
J.无法磨灭的悔恨
知识点:贪心,双指针
我们采用反悔贪心的策略。先假设所有操作均为“乘2”,然后当回撤这种操作的时候,每回撤一次就可以返还一个操作次数,然后维护这个操作过程中的max和min即可。需要注意的是,由于一个数不可能既乘2又除2,所以我们需要开两个multiset分别维护两种数:“未回撤完毕的数”和“已经回撤完毕的数”,其中未被乘2过的也属于第二种。当我们回撤时,只对第一种数的进行操作,回撤后的“除2”操作第二种数进行操作。 操作过程中,我们采取贪心策略:最开始的乘2只对最小值进行操作;后面的除2仅当同时满足【第二种数的最大值大于第一种数的最大值】以及【目前还存在由于反悔导致拥有了“除2”次数】这两种情况下才可以进行。
#include<bits/stdc++.h>
using namespace std;
multiset<pair<long long,int>>s;
multiset<long long>s2;
long long res=1e18;
void update(){
long long ma=0,mi=1e18;
if(!s.empty())ma=max(ma,s.rbegin()->first),mi=min(mi,s.begin()->first);
if(!s2.empty())ma=max(ma,*s2.rbegin()),mi=min(mi,*s2.begin());
res=min(res,ma-mi);
}
int main(){
int n,k,i,x,cnt;
cin>>n>>k;
cnt=k;
for(i=0;i<n;i++){
cin>>x;
s.insert({x,0});
}
for(i=0;i<k;i++){ //乘2操作
pair<long long,int>temp=*s.begin();
if(temp.first>1e9)break;
s.erase(s.begin());
s.insert({temp.first*2,temp.second+1});
cnt--;
}
update();
vector<pair<long long,int>>v;
for(auto i:s)v.push_back(i);
s.clear();
for(auto i:v){
if(i.second)s.insert(i);
else s2.insert(i.first);
}
while(cnt>0||!s.empty()){
pair<long long ,int>temp;
long long temp2;
if(!s2.empty())temp2=*s2.rbegin();
if(!s.empty())temp=*s.rbegin();
if(!s2.empty()&&(s.empty()||temp2>temp.first)&&cnt>0){ //除2
s2.erase(s2.find(temp2));
s2.insert(temp2/2);
cnt--;
}
else{ //对之前的乘2进行反悔
s.erase(s.find(temp));
if(temp.second==1){
s2.insert(temp.first/2);
}
else{
s.insert({temp.first/2,temp.second-1});
}
cnt++;
}
update();
}
cout<<res;
}
全部评论
(0) 回帖