A.Alice and Bob
正常打表状态转移(如果该点可以转移到0点则当前点一定赢)
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
bool vis[5005][5005];
void solve(){
int x,y;
cin>>x>>y;
cout<<(vis[x][y]?"Alice\n":"Bob\n");
}
int main()
{
for(int i=0;i<=5000;i++){
for(int j=0;j<=5000;j++){
if(vis[i][j])continue;
for(int k=1;i+k<=5000;k++)
for(int s=0;s*k+j<=5000;s++)
vis[i+k][s*k+j]=true;
for(int k=1;j+k<=5000;k++)
for(int s=0;s*k+i<=5000;s++)
vis[s*k+i][j+k]=true;
break;
}
}
ios::sync_with_stdio(false);
int t=1;
cin>>t;
while(t--)
solve();
return 0;
}
b.Ball Dropping
高中计算几何
#include <bits/stdc++.h>
#define pll __builtin_popcountll
using namespace std;
using ll = long long ;
void solve()
{
double r,a,b,h;
cin>>r>>a>>b>>h;
if(2.0*r<b){
cout<<"Drop";
return ;
}
double S=2.0*h/sqrt(4.0*h*h+(a-b)*(a-b));
double C=(a-b)/sqrt(4.0*h*h+(a-b)*(a-b));
double T=(2.0*h/(a-b));
cout<<"Stuck\n";
printf("%.10lf",r/C-b/2.0*T);
}
int main()
{
//ios::sync_with_stdio(false);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
d.Determine the Photo Position
题意:把连续m个2的1xm的串插入方框0中有几种可能(签到直接暴力就行)
#include <bits/stdc++.h>
#define pll __builtin_popcountll
using namespace std;
using ll = long long ;
char s[2002][2002];
char u[2002];
void solve()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)cin>>s[i];
cin>>u;
ll ans=0;
for(int i=0;i<n;i++){
int res=0;
for(int j=0;j<n;j++){
if(s[i][j]=='0')res++;
else {
if(res>=m)
ans+=res-m+1;
res=0;
}
}
if(res>=m)ans+=res-m+1;
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
f.Find 3-friendly Integers
找到区间内有多少个数是完美数(连续子串的和可以被3整除)
题解:
通过鸽巢原理可以发现当n>=100时候全是完美数
#include <bits/stdc++.h>
#define pll __builtin_popcountll
using namespace std;
using ll = long long ;
bool a[104];
void solve()
{
ll l,r;
cin>>l>>r;
if(l>=100){
cout<<r-l+1<<"\n";
return ;
}
ll ans=0;
for(ll i=l;i<=min(r,99*1ll);i++)
ans+=a[i];
if(r>=100)ans+=r-100+1;
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
int t=1;
for(int i=0;i<100;i++){
if(i<10){
if(i%3==0)
a[i]=true;
}
else{
int aa=i%10,bb=i/10;
if(aa%3==0||bb%3==0||(aa+bb)%3==0)a[i]=true;
}
//cout<<i<<" "<<a[i]<<endl;
}
cin>>t;
while(t--)
solve();
return 0;
}
h.Hash Function
题意:输出一个最小的数使得这个数对所有数取模可以得到n个不同的数(我当时没读懂被题目理解错了真以为是hash没想到是签到)
题解:直接枚举暴力就行
#include <bits/stdc++.h>
using namespace std;
int a[500005];
bool vis[500005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
vis[a[i]]=true;
}
sort(a+1,a+1+n);
for(int i=n;;i++){
bool f=1;
for(int j=n;a[j]>=i;j--){
if(vis[a[j]%i]){
f=0;
break;
}
}
if(f) return cout<<i,0;
}
}
k.Knowledge Test about Match
未完待续...