268C Beautiful Sets of Points

传送门
题意：在n*m的格点图里尽量多的选点，使点之间两两距离不为整数，同时不能选(0,0).
构造水题了，很明显每行/列最多放一个，那么最多应该放min(n,m)+1个，由于0,0不能选，直接从左上角走一个对角线即可。

#include<bits/stdc++.h> #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<<min(n,m)+1<<endl; for (int i = n,j=0; i >=0&&j<=m ; --i,++j) {         cout<<i<<" "<<j<<endl; } 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<bits/stdc++.h> #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 <s.size() ; ++i) { for (int j = i; j <s.size() ; ++j) {             dp[i][j]=j-i+1; } } for (int j = 1; j <s.size() ; ++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<<dp[0][s.size()-1]; return 0; } 

1251D Salary Changing

传送门
题意：公司里每个员工都有一个工资区间，你有s元，合理地分配工资，使得每个人工资都在相应区间并且工资的中位数较大。
首先贪心的想一想，既然要中位数最大，我们就让前n/2个人工资尽量少，那就是直接给下界，而后面如果要中位数尽量大，那就尽量做到平均分配，如果不能平均分配就给下界较大的人下界数额的薪水，而其余人平均分配。这个过程显然二分实现就可以了。

#include<bits/stdc++.h> #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<b.l; } ll s;int n; vector<node> 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<mid){             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<<l-1<<endl; } return 0; }