小凯逛超市
思路：其实这题和洛谷的一道题很像，都是用完全背包去统计合法次数，我们的dp[i][j]表示体积为i的价值为j的合法数量，然后直接去写一个三重循环遍历即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[405];
int dp[405][405];
int mod=1e9+7;
void solve()
{
memset(dp, 0, sizeof(dp));
int n,m,v;
cin>>n>>m>>v;
for(int i=1;i<=n;i++)
cin>>a[i];
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=v;k>=a[i];k--)
{
dp[j][k]=(dp[j][k]+dp[j-1][k-a[i]])%mod;
}
}
}
int ans=0;
for(int i=0;i<=v;i++)
ans=(ans+dp[m][i])%mod;
cout<<ans<<"\n";;
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}小凯在长跑
思路：这题就是一个纯水题了，我们根据实际生活经验也应该知道如果y坐标在-d~d之间，那么就是到两边线之间的距离最短，否则就就是到半圆，直接写即可
注意用double最后在化简成0位小数
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
double d,r,x,y;
void solve()
{
cin>>d>>r>>x>>y;
x=abs(x),y=abs(y);
if(y<=d)
{
cout<<fixed<<setprecision(0)<<abs(x-r)<<"\n";
}
else
{
cout<<fixed<<setprecision(0)<<abs(r-sqrt((x)*(x)+(y-d)*(y-d)))<<"\n";
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
solve();
return 0;
}小凯做梦
思路：这题怎么说呢？已经告诉你这个是一个n个节点的树，如果你找到三个点，他们之间的距离要同样的奇偶性，也就是说，我们找到的三个点可以连成一条线，如果旁边的两个点到中间的点是偶数就是可以的，我们可以用根节点作为校准点，分为到根节点为奇数和偶数的两个集合，每个集合的三次方的和就是最终的结果（因为到根节点为奇数距离的，他们之间的距离也相互为偶数，完全满足题意条件）
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
int t;
int n;
int u,v,w;
vector<pii> e[500005];
int a[500005];
int ans[2];
void dfs(int v,int fa)
{
ans[a[v]%2]++;
for(pii p:e[v])
{
int u=p.first;
if(u==fa)
continue;
int cnt=p.second;
a[u]=a[v]+cnt;
dfs(u,v);
}
}
void solve()
{
ans[1]=ans[0]=0;
cin>>n;
for (int i=1;i<=n;i++)
{
e[i].clear();
}
for(int i=1;i<=n-1;i++)
{
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dfs(1,0);
cout<<ans[0]*ans[0]*ans[0]+ans[1]*ans[1]*ans[1]<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
solve();
return 0;
}小凯取石子
思路：这题自己在纸上自己手推一下式子就会发现，只要n%5==2或者5那么就是百分被必输的，1，3，4则是会有自己的式子，记得用逆元去处理，直接代入即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
int mod=998244353;
int fast(int a,int b)
{
int base=1;
while(b>0)
{
if(b%2==1)
{
base=(base*a)%mod;
}
a=(a*a)%mod;
b/=2;
}
return base;
}
int inv(int x)
{
return fast(x,mod-2);
}
void solve()
{
cin>>n;
int qwq=n%5;
if (qwq==0||qwq==2)
{
cout<<"1\n";
}
else if (n%5==1)
{
int p=n/5;
int f=inv(2);
if (n==1)
p=1;
int ans=fast(f,p);
ans=(1-ans+mod)%mod;
cout<<ans%mod<<"\n";
}
else if (n%5==3)
{
int p=n/5+2;
int f=inv(2);
int ans=fast(f,p);
ans=(1-ans+mod)%mod;
cout<<ans%mod<<"\n";
}
else if (n%5==4)
{
int p=n/5+1;
int f=inv(2);
int ans=fast(f,p);
ans=(1-ans+mod)%mod;
cout<<ans%mod<<"\n";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t;
while (t--)
solve();
return 0;
}
小凯想要MVP!
这题怎么说呢？感觉就是莫名奇妙的就过了，只处理两种情况即可，第一种是用bitset去判断是否有一个数出现了两次，如果有，那就直接输出yes，然后返回，否则再去判断是否有两个数相加可能会出现两次，如果有那就输出yes，否则就是no
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int c[200005];
bitset<400005> b;
void solve()
{
cin>>n>>m;
bool flag=false;
for(int i=1;i<=m;i++)
{
b[i]=0;
}
for(int i=1;i<=n;i++)
{
cin>>c[i];
if(b[c[i]])
{
flag=true;
}
b[c[i]]=1;
}
if(flag)
{
cout<<"YES\n";
return;
}
for(int i=1;i<=(m<<1);i++)
{
b[i]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int x=c[i]+c[j];
if(b[x])
{
cout<<"YES\n";
return;
}
b[x]=1;
}
}
cout<<"NO\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}