- 有问题联系QQ:2463973240
A:思维题
首先等于的时候一定是全真,先开一个bool数组记录全真的情况,其次我们发现要是假硬币更重,则大于的时候假硬币在左边,小于的时候假硬币在右边,我们可以开辟一个r数组记录(大于的时候)左边天平全加一(小于的时候)右边的天平全加一,同理开辟l数组与其记录相反,这样的话假硬币如果heavy那么他的r值一定等于大于和小于号出现的次数,如果light同理
#include<iostream>
using namespace std;
int f[5][30]={
{1,2,7,8,13,14,19,20,25,26,31,32,37,38,0,4,5,10,11,16,17,22,23,28,29,34,35,40},
{0,3,6,11,13,14,16,21,24,29,31,32,34,39,2,4,5,7,12,15,20,22,23,25,30,33,38,40},
{5,7,9,11,13,14,16,18,20,22,33,35,37,39,0,6,8,10,12,15,17,19,21,32,34,36,38,40},
{0,15,17,19,21,23,25,27,29,31,33,35,37,39,14,16,18,20,22,24,26,28,30,32,34,36,38,40}
};
bool st[50];
int l[50],r[50];
int main()
{
string s;
while(cin>>s)
{
for(int i=0;i<50;i++) st[i]=0,l[i]=0,r[i]=0;
int cnt=0;
for(int i=0;i<4;i++)
{
if(s[i]=='=')
for(int j=0;j<28;j++) st[f[i][j]]=true;
else if(s[i]=='>')
{
for(int j=0;j<14;j++) r[f[i][j]]++;
for(int j=14;j<28;j++) l[f[i][j]]++;
cnt++;
}
else
{
for(int j=0;j<14;j++) l[f[i][j]]++;
for(int j=14;j<28;j++) r[f[i][j]]++;
cnt++;
}
}
st[0]=1;
for(int i=0;i<41;i++)
{
if(l[i]==cnt&&!st[i]) cout<<i<<' '<<"light"<<endl;
else if(r[i]==cnt&&!st[i]) cout<<i<<' '<<"heavy"<<endl;
}
}
}
C:数论题
按照一般的思路快速幂前缀和是可以很简单就过的,但是观察数据范围1e7加log明显会T所以我们要找到一个线性并且常数不太大的算法,自然而然就想到了线性筛,正好符合性质,例如6^k明显等于(2*3)^k,根据线性筛,筛的过程中把快速幂更新,这样就完美的去掉了一个log,不去log的快读应该也会T以上是正解,记得开long long记得拒绝cin,cout
#include<iostream>
using namespace std;
const int N=1e7+10,mod=998244353;
typedef long long ll;
ll f[N],g[N];
bool st[N];
ll k,m,cnt;
ll qpow(ll a,ll k)
{
ll res=1;
while(k)
{
if(k&1) res=(res*a)%mod,res%=mod;
k>>=1,a=(a*a)%mod;
a%=mod;
}
return res%mod;
}
void init()
{
f[1]=1;
for(int i=2;i<N-6;i++)
{
if(!st[i])
{
g[++cnt]=i;
f[i]=qpow(i,k)%mod;;
}
for(int j=1;j<=cnt&&i*g[j]<=N-6;j++)
{
st[i*g[j]]=true;
f[i*g[j]]=(f[i]*f[g[j]])%mod;
if(i%f[j]==0)break;
}
}
}
int main()
{
scanf("%d%d",&k,&m);
init();
for(int i=1;i<N-6;i++) f[i]=(f[i]+f[i-1])%mod;
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",(f[r]-f[l-1]+mod)%mod);
}
return 0;
}
D:博弈论
很明显先手一直保持拿后是偶数稳赢,因为绝顶聪明一堆中如果是奇数个石子不管怎么拿先手与后手拿完这堆都会交换次序,同理偶数堆拿完等于没拿,所以答案只与奇数堆的个数有关,奇数堆有奇数个则先手必胜,反之先手必败
#include<iostream>
using namespace std;
int main()
{
int t ;cin>>t;
while(t--)
{
int n;cin>>n;
int ans=0;
while(n--)
{
int p;cin>>p;
if(p&1) ans+=1;
}
if(ans&1) puts("Alice");
else puts("Bob");
}
}
H:搜索题
很简单,由于P的移动速度大于X只要静态的P能走到X,则P一定能抓到X,bfs的板子
#include<iostream>
#include<queue>
using namespace std;
const int N=110;
char a[N][N];
bool st[N][N];
int n,m;
int sx,sy,ex,ey;
typedef pair<int,int> p;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool bfs(int x,int y)
{
queue<p>q;
q.push({x,y});
st[x][y]=true;
while(q.size())
{
p t=q.front();
q.pop();
int c=t.first,b=t.second;
if(c==ex&&b==ey)
{
return true;
}
for(int i=0;i<4;i++)
{
int l=c+dx[i],r=b+dy[i];
if(l<1||l>n||r<1||r>m||a[l][r]=='o'||st[l][r]) continue;
q.push({l,r});
st[l][r]=true;
}
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]=='P') sx=i,sy=j;
if(a[i][j]=='X') ex=i,ey=j;
}
}
if(bfs(sx,sy)) puts("Playftql");
else puts("Playftcl");
}
J:签到题
很简单的签到题根据题意列出线方程带入x1,x2判断函数值与y1,y2的关系要是全大于或者全小于则在一侧,反之不在一侧,特判B等于0的情况
#include<iostream>
using namespace std;
int main()
{
int t;cin>>t;
while(t--)
{
double x1,y1,x2,y2,a,b,c;
cin>>x1>>y1>>x2>>y2>>a>>b>>c;
if(b==0)
{
double l=-c/a;
if(x1>=l&&x2>=l||x1<=l&&x2<=l) puts("Yes");
else puts("No");
continue;
}
double k=-a/b;
double q=-c/b;
double y11=k*x1+q,y22=k*x2+q;
if(y11>y1&&y22>y2||y11<y1&&y22<y2) puts("Yes");
else puts("No");
}
}
K:签到题
观察发现,每层恰好是2的k次幂直接快速幂加前缀和行
#include<iostream>
using namespace std;
const int N=1e6+10,mod=1e9+7;
typedef long long ll;
ll f[N];
ll qpow(ll k)
{
ll ans=1;
ll base=2;
while(k)
{
if(k&1)ans=(ans*base)%mod;
k>>=1,base=(base*base)%mod;
}
return ans%mod;
}
int main()
{
int n;cin>>n;
ll ans=0;
for(int i=1;i<=n;i++)
f[i]=qpow(i-1),ans+=f[i],ans%=mod;
cout<<ans<<endl;
return 0;
}
L:高精度
py不到10行
t=int(input())
for i in range(0,t):
a,b=map(str,input().split(' '))
a=int(a,16)
b=int(b,16)
if((2*a+10)>(3*b+5)):
print("Yes")
else:
print("No")
正常的高精套上板子80来行,没有感情全是技巧
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
map<char,int>mp;
vector<int> add(vector<int>&A,vector<int>&B)
{
vector<int>c;
int t=0;
for(int i=0;i<A.size()||i<B.size();i++)
{
if(i<A.size())t+=A[i];
if(i<B.size())t+=B[i];
c.push_back(t%16);
t/=16;
}
if(t)c.push_back(t);
return c;
}
vector<int> cum(vector<int>&A,int b)
{
int t=0;
vector<int>c;
for(int i=0;i<A.size();i++)
{
t+=A[i]*b;
c.push_back(t%16);
t/=16;
}
while(t)
{
c.push_back(t%16);
t/=16;
}
while(c.size()>1&&c.back()==0)c.pop_back();
return c;
}
int main()
{
mp['0']=0,mp['1']=1,mp['2']=2;
mp['3']=3,mp['4']=4,mp['5']=5;
mp['6']=6,mp['7']=7,mp['8']=8;
mp['9']=9;
mp['A']=10,mp['B']=11,mp['C']=12;
mp['D']=13,mp['E']=14,mp['F']=15;
int t ;cin>>t;
while(t--)
{
string s,ss;
cin>>s>>ss;
vector<int>v1,v2,v3,v4;
for(int i=s.size()-1;i>=0;i--) v1.push_back(mp[s[i]]);
for(int i=ss.size()-1;i>=0;i--) v2.push_back(mp[ss[i]]);
vector<int>ans1=cum(v1,2);
vector<int>ans2=cum(v2,3);
v3.push_back(10),v4.push_back(5);
ans1=add(ans1,v3),ans2=add(ans2,v4);
string str1,str2;
for(int i=ans1.size()-1;i>=0;i--)
{
if(ans1[i]>=0&&ans1[i]<=9)
str1+=ans1[i]+'0';
else str1+=ans1[i]-10+'A';
}
for(int i=ans2.size()-1;i>=0;i--)
{
if(ans2[i]>=0&&ans2[i]<=9)
str2+=ans2[i]+'0';
else str2+=ans2[i]-10+'A';
}
if(str1.size()>str2.size()) puts("Yes");
else if(str1.size()==str2.size())
{
if(str1>str2) puts("Yes");
else puts("No");
}
else puts("No");
}
}