只过了ADFGJ
其他待补
A 贪心
考虑一下，如果数字一样，这人还是会排在前面的所有人里的最后一名，那么m肯定先给自己加一个，然后因为≥他的人不管加不加都在他前面，所以给数字≥他的都加上，如果m还有剩余，考虑从最小的加，尽量减少他后面的人谁提高到和他一样(因为他字典序最大)
所以排序一下，对他前面的人进行加，还有剩余，就从最小的开始加。再次排序找他的名次即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll x;
ll id;
} a[200005];
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i].x;
a[i].id = i;
}
a[1].x++;
ll e = a[1].x;
m--;
sort(a + 1, a + 1 + n, [](node a, node b) {
if (a.x != b.x)
return a.x < b.x;
return a.id < b.id;
});
int k = 0;
for (int i = 1; i <= n && m; i++)
{
if (a[i].id == 1)
{
k = i;
continue;
}
if (a[i].x >= e)
a[i].x++, m--;
}
for (int i = 1; m && i < k; i++)
{
a[i].x++, m--;
}
sort(a + 1, a + 1 + n, [](node a, node b) {
if (a.x != b.x)
return a.x < b.x;
return a.id < b.id;
});
int flag = 0;
for (int i = n; i; i--)
{
if (a[i].id == 1)
{
flag = n - i + 1;
break;
}
}
cout << flag << endl;
}
return 0;
}D 简单数学
n个人可以看成一个集合，那么一个集合中，有 个子集，因为每个子集要么有这个人，要么没这个人。
那么刨除这个当队长的人，还有n-1个人，也就是还有 个集合，有m个人能当队长，答案自然就是
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=a*ans%mod;
a=a*a%mod;
b/=2;
}
return ans;
}
int main(){
int t;cin>>t;
while(t--){
ll n,m;cin>>n>>m;
cout<<m*qpow(2,n-1)%mod<<endl;
}
return 0;
}F 简单找规律
可以发现第n个字符串中，第一个串出现的次数是 次 第二个串出现的次数是
次
其中f是斐波那契数列。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll f[45];
int main()
{
ll s[130] = {0}, d[130] = {0};
string a, b;
cin >> a >> b;
int n;
cin >> n;
f[1] = f[2] = 1;
for (int i = 3; i <= n; i++)
{
f[i] = f[i - 1] + f[i - 2];
}
ll q, w;
if (n >= 3)
q = f[n - 2], w = f[n - 1];
else if (n == 1)
q = 1, w = 0;
else
q = 0, w = 1;
for (int i = 0; a[i]; i++)
s[a[i]]++;
for (int i = 0; b[i]; i++)
d[b[i]]++;
for (int i = 'A'; i <= 'Z'; i++)
{
if (s[i]&&q || d[i]&&w)
cout << (char)i << ": " << s[i]*q + d[i]*w << endl;
}
for (int i = 'a'; i <= 'z'; i++)
{
if (s[i]&&q || d[i]&&w)
cout << (char)i << ": " << s[i]*q + d[i]*w << endl;
}
return 0;
}G 博弈思想
考虑一下，最后的答案其实是取决于第三个人，因为他是最后一个剔除最后一个数的人。
那么他想要的肯定是要离0近的，那么第二个人就要去考虑第三个人怎么想的，第三个人肯定取离0近的，所以固定第一个人，固定第二个人后得到的和后取最小，这是第三个人想要的，那么回到第二个人，固定第一个人，枚举第二个人，他想要最小的，所以就是所有的离0近的里在取最小的。
那么对于第一个人要最大的，他就要考虑第二个人第三个人的情况，所以答案就是离0近的里最小的里的最大的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int a[105], b[105], c[105];
ll q[105];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int j = 1; j <= n; j++)
cin >> b[j];
for (int k = 1; k <= n; k++)
cin >> c[k];
ll ma=-1e9;
for (int o = 1; o <= n; o++)
{
ll ans = 1e9,x=a[o];
for (int i = 1; i <= n; i++)
{
int cnt = 0;
for (int j = 1; j <= n; j++)
{
q[++cnt] = b[i] + c[j] + x;
}
sort(q + 1, q + 1 + cnt);
int k = lower_bound(q + 1, q + 1 + cnt, 0) - q;
ll sum;
if (k == cnt + 1)
sum = q[k - 1];
else
{
if (k == 1)
sum = q[k];
else
{
if (q[k] > -q[k - 1])
sum = q[k - 1];
else
sum = q[k];
}
}
ans = min(ans, sum);
}
ma=max(ma,ans);
}
cout << ma << endl;
return 0;
}J 组合数学 卡特兰数+可重集排列数
容易发现，一个右上走+一个右下走就等于一个往右走两步。
考虑一下第一个点，不能走到y下面，对y坐标影响的只有右上和右下，那么我们把右上看成一个左括号，右下看成一个右括号，求合法括号方案数，那么其实方案数就是一个卡特兰数。
那么这样的话，对于右上右下的已经处理好了，还差一个直接往右走的有i个，那么考虑这两部分结合，容易发现是一个可重集排列数，那么对于每个合法括号数里结合i个直接往右走的方案数有
其中分子就是总的组成个数，右上右下总共有2(n-i)个，直接右走有i个,所以一共是2n-i个。
那么最后答案就是
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll qpow(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = a * ans % mod;
a = a * a % mod;
b /= 2;
}
return ans;
}
ll f[300005];
int main()
{
f[0]=1;
for(int i=1;i<=300000;i++){
f[i]=f[i-1]*i%mod;
}
int n;cin>>n;
ll ans=0;
for(int i=0;i<=n;i++){
ll sum=1;
ll cat=f[2*(n-i)]*qpow(f[(n-i)]*f[(n-i)]%mod*((n-i)+1)%mod,mod-2)%mod;//卡特兰数部分
sum=f[2*n-i]*qpow(f[i]*f[2*(n-i)]%mod,mod-2)%mod;//可重集部分
ll q=cat%mod*sum%mod;
ans=(ans+q)%mod;
}
cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号