数学题做爽了
A.台阶问题
lnk
简单记搜，但是忘记取模……赛时没过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<bits/stdc++.h>
using namespace std;
#define mod 100003
int f[100010],n,k;
int dfs(int n)
{
if(n<0)return 0;
if(f[n])return f[n];
int res=0;
for(int i=1;i<=k;i++)
res+=dfs(n-i);
return f[n]=res%mod;
}
int main()
{
cin>>n>>k;
f[0]=1;
f[1]=1;
cout<<dfs(n);
return 0;
}
|
B.[USACO17OPEN] Bovine Genomics S
lnk
666，这题是暴力，我以为是什么高端做法，后面想到暴力但是暴力没打出来🤦，有救吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<bits/stdc++.h>
using namespace std;
const int MAXN=510;
int n,m,ans;
string dot[MAXN],nor[MAXN];
map<char,int> p{{'A',1},{'C',2},{'G',3},{'T',4}};
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>dot[i];
for(int i=0;i<n;i++)
cin>>nor[i];
for(int i=0;i<m-2;i++)
for(int j=i+1;j<m-1;j++)
for(int k=j+1;k<m;k++)
{
bool flag=1;
bool vis[64]={0};
for(int l=0;l<n;l++)
{
int a=p[dot[l][i]]-1;
int b=p[dot[l][j]]-1;
int c=p[dot[l][k]]-1;
int key=(a<<4)|(b<<2)|c;
vis[key]=true;
}
for(int l=0;l<n;l++)
{
int a=p[nor[l][i]]-1;
int b=p[nor[l][j]]-1;
int c=p[nor[l][k]]-1;
int key=(a<<4)|(b<<2)|c;
if(vis[key])
{
flag=0;
break;
}
}
ans+=flag;
}
cout<<ans;
return 0;
}
|
D. [Cnoi2019] 数学作业
lnk
还是不会，数学题太难了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
unsigned long long qpow(unsigned long long a,unsigned long long b)
{
unsigned long long ans=1;
a%=mod;
while(b)
{
if(b&1)
ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
unsigned long long sum=0;
for(int i=0;i<n;i++)
{
unsigned long long tmp;
cin>>tmp;
sum|=tmp;
}
unsigned long long result=(sum%mod)*qpow(2,n-1)%mod;
cout<<result<<'\n';
}
return 0;
}
|
D.[USACO17JAN] Building a Tall Barn P
仍然数学题，虽然看上去很程序，标签是二分，但是二分的是柿子，是真的不会啊
不知道为啥是87分，没找到问题……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+10;
double a[MAXN],ans;
int n,k;
bool check(double t)
{
int cnt=0;
for(int i=1;i<=n;i++)
{
double x=sqrt(1+4*a[i]/t);
cnt+=(double)(ceil((x-1)/2));
}
return cnt<=k;
}
signed main()
{
cin>>n>>k;
double mx=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mx=max(mx,a[i]);
}
double l=1e-12,r=2*mx;
while(r-l>1e-12)
{
double mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;
}
int sum=0;
for(int i=1;i<=n;i++)
{
double x=sqrt(1+4*a[i]/r);
int v=ceil((x-1)/2);
ans+=a[i]/v;
sum+=v;
}
if(sum<k)
{
double diff=k-sum;
ans-=diff*r;
}
cout<<round(ans);
}
|