A.Ichihime and Triangle 题目链接
贪心就好啦，让两条长边一样长就肯定能形成三角形
#include
using namespace std;
typedef long long ll;
typedef pair pll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const int inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const int maxn=1e5+10;
ll a,b,c,d;
void solve()
{
rd(a),rd(b),rd(c),rd(d);
printf("%lld %lld %lld\n",b,c,c);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("stdin.in","r",stdin);
//freopen("stdout.out","w",stdout);
#endif ll T;
rd(T);
while(T--) solve();
return 0;
}
B.Kana and Dragon Quest game 第一种魔法在hp大于20的时候才能产生收益，所以我们先用第一种魔法，把hp降到20以下或者第一种魔法达到它的最大使用次数，然后判断用第二种魔法是否能消灭
#include
using namespace std;
typedef long long ll;
typedef pair pll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const int inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const int maxn=1e5+10;
ll x,n,m;
void solve()
{
rd(x),rd(n),rd(m);
while(x>20&&n>0)
{
n--;
x=x/2+10;
}
if(x>m*10)
{
puts("NO");
return;
}
puts("YES");
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("stdin.in","r",stdin);
//freopen("stdout.out","w",stdout);
#endif ll T;
rd(T);
while(T--) solve();
return 0;
}
C.Linova and Kingdom 这题很明显是一个贪心吧，选取总收益最高的k个节点作为工业。
首先，假设你选了一个点为工业，那么它的正面收益很明显就是他的深度，但这题很多人（包括我）第一遍做的时候，忽略了选这个点为工业的负面收益，也就是这个点下面的子节点数。
那么为什么会产生这个负面收益呢？
因为这题我们使用了贪心策略，所以如果你选的这个点下面还有子节点，那么我们必然会选择它的子节点。
所以一旦我们选择了某个节点作为工业，就意味着它所有的子节点已经被我们选为工业，那么它的子节点在经过它的时候将不会产生收益，也就是这些子节点经过这个节点的收益从1下降至0，一共下降了子节点数的收益。
即这个点的真正收益为节点深度-子节点数。
用我代码中注释掉的那句话就可以看到每个节点的真正收益。
#include
using namespace std;
typedef long long ll;
typedef pair pll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const int inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const int maxn=2e5+10;
int n,k,x,y,a[maxn];
vectorm[maxn];
bool cmp(int a,int b)
{
return a>b;
}
ll dfs(int now,int steps,int pre)
{
int temp=0;
for(int i=0;
i D.Xenia and Colorful Gems 【补题|Codeforces Round #635 (Div. 2)】把rgb三种颜色的大小排个序，然后二分查找一下就出来了。
就是先枚举一个颜色中的一个，然后从另外两种颜色中找出和它最接近的两个，更新一下答案
（我觉得就是一个无脑暴力题）
#include
using namespace std;
typedef long long ll;
typedef pair pll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const ll inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const ll maxn=2e5+10;
ll nr,ng,nb,R[maxn],G[maxn],B[maxn],pos1,pos2;
ll distance(ll t1,ll t2,ll t3)
{
return (t1-t2)*(t1-t2)+(t1-t3)*(t1-t3)+(t2-t3)*(t2-t3);
}
ll minn(ll a,ll b,ll c,ll d)
{
return min(min(min(a,b),c),d);
}
ll judge(ll a1[],ll n1,ll a2[],ll n2,ll a3[],ll n3){
ll now=INF;
for(ll i=1;
i<=n1;
++i)
{
pos1=lower_bound(a2+1,a2+1+n2,a1[i])-a2;
pos2=lower_bound(a3+1,a3+1+n3,a1[i])-a3;
if(pos1>1&&(pos1>n2||a2[pos1]>a1[i])) --pos1;
if(pos1<=n2&&pos2<=n3) now=min(now,distance(a1[i],a2[pos1],a3[pos2]));
pos1=lower_bound(a3+1,a3+1+n3,a1[i])-a3;
pos2=lower_bound(a2+1,a2+1+n2,a1[i])-a2;
if(pos1>1&&(pos1>n3||a3[pos1]>a1[i])) --pos1;
if(pos1<=n3&pos2<=n2) now=min(now,distance(a1[i],a3[pos1],a2[pos2]));
}
return now;
}
void solve()
{
ll ans=INF;
rd(nr),rd(ng),rd(nb);
for(ll i=1;
i<=nr;
i++) rd(R[i]);
for(ll i=1;
i<=ng;
i++) rd(G[i]);
for(ll i=1;
i<=nb;
i++) rd(B[i]);
sort(R+1,R+1+nr);
sort(G+1,G+1+ng);
sort(B+1,B+1+nb);
ans=minn(ans,judge(R,nr,B,nb,G,ng),judge(B,nb,R,nr,G,ng),judge(G,ng,R,nr,B,nb));
printf("%lld\n",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("stdin.in","r",stdin);
//freopen("stdout.out","w",stdout);
#endif ll T;
rd(T);
while(T--) solve();
return 0;
}
E.Kaavi and Magic Spell
#include
using namespace std;
typedef long long ll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const int inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const int maxn=3e3+10;
const int mod=998244353;
int n,m,dp[maxn][maxn];
string s,t;
void solve()
{
cin>>s>>t;
n=s.size(),m=t.size();
for(int i=1;
i<=n+1;
i++) dp[i][i-1]=1;
for(int i=1;
i<=n;
i++)
{
for(int j=1,k=i;
k<=n;
j++,k++)
{
if(j>m||t[j-1]==s[i-1]) dp[j][k]=(dp[j][k]+dp[j+1][k])%mod;
if(k>m||t[k-1]==s[i-1]) dp[j][k]=(dp[j][k]+dp[j][k-1])%mod;
}
}
int ans=0;
for(int i=m;
i<=n;
i++) ans=(ans+dp[1][i])%mod;
printf("%d\n",ans);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("hzh.in","r",stdin);
#endif
/*
ll T;
rd(T);
while(T--)
*/
solve();
return 0;
}
推荐阅读
- 补题|Educational Codeforces Round 85 (Rated for Div. 2)
- everyday|Codeforces Round #634 (Div. 3)
- 补题|Codeforces Round #633 (Div. 2)
- Codeforces Round #623
- 补题|Omkar and Bed Wars
- Codeforces Round #609 (Div. 2)
- 牛妹爱数列