1.Game on Ranges
原题链接：http://162.14.124.219/contest/1011/problem/B
看懂英文后进行排序，按照区间长度从短到长，起始数字从小到大来排序，再依次标记赋值，模拟这个过程即可
查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000000],b[1000000],c[1000000],id[1000000];
bool cmp(int x,int y)
{
if(b[x]-a[x]==b[y]-a[y])return a[x]<a[y];
return b[x]-a[x]<b[y]-a[y];
}
signed main() {
int t;
cin>>t;
while(t--) {
int n;
cin>>n;
map<int,int>mp,dp;
mp.clear(),dp.clear();
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
id[i]=i;
if(a[i]==b[i])mp[i]++,dp[a[i]]++,c[i]=a[i];
}
sort(id+1,id+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(mp[id[i]])continue;
else
{
for(int j=a[id[i]];j<=b[id[i]];j++)
{
if(!dp[j])
{
c[id[i]]=j;
dp[j]++;
}
}
}
}
for(int i=1;i<=n;i++)
{
cout<<a[id[i]]<<" "<<b[id[i]]<<" "<<c[id[i]]<<endl;
}
cout<<endl;
}
return 0;
}2.Bouquet
原题链接：http://162.14.124.219/contest/1011/problem/E
总方案数减去选A个数字的方案数减去选B个数字的方案数再减去空集，2n-Can-Cbn-1即为所求
查看代码
#include<bits/stdc++.h>
#define int long long
const int N=3e5+5;
const int M=3e5;
using namespace std;
const int mod=1e9+7;
int n,a,b,inv[N];
int ksm(int x,int y)
{
int ans=1;
while(y)
{
if(y&1)ans=ans*x%mod;
x=x*x%mod,y>>=1;
}
return ans;
}
int C(int n,int m)
{
int ans=1;
for(int i=1;i<=m;i++)
{
ans=ans*(n-m+i)%mod*inv[i]%mod;
}
return ans;
}
signed main()
{
cin>>n>>a>>b;
for(int i=1;i<=M;i++)inv[i]=ksm(i,mod-2);
int ans=(ksm(2,n)-C(n,a)-C(n,b)-1+3*mod)%mod;
cout<<ans;
}3.String Cards
原题链接：http://162.14.124.219/contest/1011/problem/G
按照cmp的标准排序后再进行从后往前的递推简单dp，记得先初始化成无穷大
查看代码
#include <bits/stdc++.h>
using namespace std;
string s[10000],dp[1000][1000];
inline bool cmp(string a,string b){
return a + b < b + a;
}
int main() {
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>s[i];
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
dp[i][j]="}";
dp[n][1]=s[n];
for(int i=n-1;i>=1;i--)
{
for(int j=1;j<=k;j++)
{
dp[i][j]=min(dp[i+1][j],s[i]+dp[i+1][j-1]);
}
}
// for(int i=1;i<=n;i++) {
// for (int j = 1; j <= k; j++)
// cout << dp[i][j] << " ";
// cout<<endl;
// }
cout<<dp[1][k];
return 0;
}