Codeforces每日一练268C+1132F+1251D

268C Beautiful Sets of Points

传送门

题意：在n*m的格点图里尽量多的选点，使点之间两两距离不为整数，同时不能选(0,0).

构造水题了，很明显每行/列最多放一个，那么最多应该放min(n,m)+1个，由于0,0不能选，直接从左上角走一个对角线即可。

#include
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define ll long long
#define maxn 200006
signed main()
{
IOS
int n,m;
cin>>n>>m;
cout< for (int i = n,j=0; i >=0&&j<=m ; --i,++j) {
cout< }
return 0;
}

1132F Clear the String

传送门

题意：每次可以删除一个只含一种字符的子串，最少多少次可以删完整个字符串。

一遇区间dp就萎

（其实这道题和HDU上一道区间很像，HDU 2476 String painter）

两道题大致思路都是枚举右端点，然后从右端点左移左端点，然后从左向右扫。这道题里我们可以开一个二维数组记录i到j的最小代价，而每个dp[i][j]可能是[i-1][j]来的，也可能是[i][j-1]来的，所以先传递之前求出的最小值，之后就是从左向右扫，如果s[k]=s[i]，那么我们删k的时候就可以把i也删了，这时候的代价就是dp[i+1][k-1]+dp[k][j]，扫的时候转移即可。

#include
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define ll long long
#define maxn 505
int dp[maxn][maxn];
signed main()
{
IOS
int n;
cin>>n;
string s;
cin>>s;
for (int i = 0; i for (int j = i; j dp[i][j]=j-i+1;
}
}
for (int j = 1; j for (int i = j-1; i >=0 ; --i) {
dp[i][j]=min(dp[i][j],min(dp[i][j-1]+1,dp[i+1][j]+1));
for (int k = i; k <=j ; ++k) {
if(s[k]==s[i]){
dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);
}
}
}
}
cout< return 0;
}

1251D Salary Changing

传送门

题意：公司里每个员工都有一个工资区间，你有s元，合理地分配工资，使得每个人工资都在相应区间并且工资的中位数较大。

首先贪心的想一想，既然要中位数最大，我们就让前n/2个人工资尽量少，那就是直接给下界，而后面如果要中位数尽量大，那就尽量做到平均分配，如果不能平均分配就给下界较大的人下界数额的薪水，而其余人平均分配。这个过程显然二分实现就可以了。

#include
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define ll long long
#define maxn 200006
struct node{
ll l,r;
}m[maxn];
bool cmp(node a,node b){
return a.l}
ll s;int n;
vector g;
int check(ll mid){
g.clear();
ll ans=0;
int cnt=0,cnt1=0,cnt2=0;
for (int i = 1; i <=n ; ++i) {
if(m[i].r cnt1++;
ans+=m[i].l;
}
else if(m[i].l>mid){
cnt2++;
ans+=m[i].l;
}else{
cnt++;
g.push_back(m[i]);
}
}
if(cnt1>n/2)return 0;
else if(cnt2>n/2)return 1;
else{
for (int i = 0; i <(n/2)-cnt1 ; ++i) {
ans+=g[i].l;
}
ans+=mid*(n/2+1-cnt2);
return ans<=s;
}
}
signed main()
{
IOS
int t;
cin>>t;
while(t--){
cin>>n>>s;
for (int i = 1; i <=n ; ++i) {
cin>>m[i].l>>m[i].r;
}
sort(m+1,m+1+n,cmp);
ll l=m[n/2+1].l,r=s/(n/2+1),mid,tmp;
while(l<=r){
mid=(l+r)/2;
if(check(mid)){
l=mid+1;
}
else r=mid-1;
}
cout< }
return 0;
}