ABC-167-A,B,C,D,E
打卡8/6 感觉最近的想法题反应太慢了，打几把ABC压压惊，下回争取开到E
A - Registration
题意：
给你两个字符串s,t，问你t是不是只比s多最后一个字母
思路：
可以通过给s填一个字母或给t删掉最后一个字母来比较
签到题拼手速
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a) & -(a))
#define clean(a, b) memset(a, b, sizeof(a))
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 9;
int _;
//========================================================================
//========================================================================
int main()
{
string a,b;
cin>>a>>b;
int len=b.size();
a+=b[len-1];
if(a==b)puts("Yes");
else puts("No");
return 0;
}
B - Easy Linear Programming
题意：
给你A,B,C,K，分别代表你有A个1，B个0，C个-1，想取K个数，取到的最大权值是多少？
思路：
贪心的想自然是优先取A然后B，C
手速题
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a) & -(a))
#define clean(a, b) memset(a, b, sizeof(a))
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 9;
int _;
//========================================================================
int a[5];
//========================================================================
int main()
{
for(int i=1;i<=3;i++)
{
scanf("%d",&a[i]);
}
int k,ans=0;
scanf("%d",&k);
if(a[1]>k) ans+=k,k=0;
else ans+=a[1],k-=a[1];
if(a[2]>k) k=0;
else k-=a[2];
if(a[3]>k) ans-=k,k=0;
else ans-=a[3],k-=a[3];
printf("%d
",ans);
return 0;
}
C - Skill Up
题意：
书店有n本书，每本书都讲了m种算法，学会了这个算法，对他的理解就增加a[i][j]，每本书都有自己的价钱，问至少买哪几本书，能使花费最小，但对每个算法的理解都达到了x
思路：
我就是最后这里没有念懂题QAQ
n,m很小，可以枚举，官方题解是dfs，状压枚举也可以，对于每一本书，都有选和不选两种选择，所以可以用二进制的 ( ( 1 << n ) - 1 ) 来表示所有情况，暴力就可以了
我发誓以后的easy题我指定先考虑暴力
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a) & -(a))
#define clean(a, b) memset(a, b, sizeof(a))
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 9;
int _;
//========================================================================
int a[20][20],ans[20],c[20];
//========================================================================
int main()
{
int n,m,x;
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
int base=(1<<n),minn=inf;
for(int i=1;i<base;i++)
{
clean(ans,0);
int val=0;
for(int j=0;j<n;j++)
{
if(((i>>j)&1)==1)
{
val+=c[j+1];
for(int k=1;k<=m;k++)
{
ans[k]+=a[j+1][k];
}
}
}
int flag=0;
for(int k=1;k<=m;k++)
{
if(ans[k]<x) flag++;
}
if(flag==0) minn=min(minn,val);
}
if(minn==inf) minn=-1;
printf("%d
",minn);
return 0;
}
D - Teleporter
题意：
有n个城市，每个城市都指向一个城市，从1开始，你想走k个地方，问走完这k个地方到达的是第几个城市
思路：
k 1e18，模拟就不要想了嗷，因为一共就n个城市，所以你走完这n个城市后就一定是循环的了，找到前缀为x，循环结为y，用b数组把路径上的城市记下来，mod=(k-x)%y，如果mod==0，证明是循环的最后一位，ans=b[y+x]，否则，ans=b[mod+x];哦对，还要判断一下是不是还没开始循环就到地方了，如果是，直接输出即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a) & -(a))
#define clean(a, b) memset(a, b, sizeof(a))
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 9;
int _;
//========================================================================
int a[maxn],vis[maxn],b[maxn];
//========================================================================
int main()
{
int n;
ll k;
scanf("%d%lld",&n,&k);
k++;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int pos=1,x,y,ans_;
vis[1]=1;
b[1]=1;
for(int i=2;i<=n+1;i++)//要跑到n+1因为想要到达所有的城市回到1 就是n+1
{
pos=a[pos];
b[i]=pos;
if(vis[pos])
{
x=vis[pos]-1;
y=i-vis[pos];
break;
}
vis[pos]=i;
}
if(k>=(x+y))
{
int ans=(k-x)%y;
if(ans==0) ans=b[y+x];
else ans=b[ans+x];
printf("%d
",ans);
}
else
{
printf("%d
",b[k]);
}
return 0;
}
/*
6 5
3 6 5 4 2 1
*/
E - Colorful Blocks
题意：
在(1-m)中选(n)个数排列，要求最多只有(k)组两个一样的连在一起，问不一样的排列有多少种？？
思路：
我排列组合怕是白学了，没想到，主要是还没太整明白，看了题解才知道dp的思路也能做（实现不了），dp[选了i个数][有j组一样的连在一起]，(dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*(m-1)) 增加了连在一起的组数的话，那他的颜色就是固定的，就是1，每增加就是（m-1）有一种不能选
然后就可以经过一系列的推导 得出结论（其实把这个数组展开 巴拉巴拉 加一下）
当然(dp)的思路清楚了的话，组合数学也就不难理解了，设有(j)个位置的相邻是相同的，一共(n-1)个位置（他占的是两个数中间的缝）就是(C_{n-1}^{j})，然后有(m)个数字，就是(m*C_{n-1}^{j})，再看剩下的位子，(j)个位置相邻，有(j+1)个位置已经被占上了，剩下((n-1-j))个，每个位置都可以选((m-1))个数，就是((m-1)^{n-i-j})乘到一起，(ans=m*C_{n-1}^{j}*(m-1)^{n-i-j}).
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a) & -(a))
#define clean(a, b) memset(a, b, sizeof(a))
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 9;
int _;
//========================================================================
ll pr[maxn];
void init()
{
pr[0]=1;
for(int i=1;i<=maxn;i++)
{
pr[i]=pr[i-1]*i%mod;
}
}
ll fpow(ll a,ll b)
{
a%=mod;
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans%mod;
}
ll c(ll a,ll b)
{
if (a < b || a < 0 || b < 0) return 0;
return pr[a]*fpow(pr[b]*pr[a-b]%mod,mod-2)%mod;
}
//========================================================================
int main()
{
init();
int n,m,k,ans=0;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=k;i++)
{
ans=(ans+(m*c(n-1,i)%mod)*fpow(m-1,n-1-i)%mod)%mod;
}
printf("%d
",ans);
return 0;
}