昨天的一道题，Mathmen。

Mathmen（贪心，二分）

题意：

给定n个位置，和m个船只，要从一个位置到后面一个位置挨个走。
每只船只都有两种属性：行驶距离和花费。
每个位置都有m条船，从一个位置到下一位置选择一艘船，行驶距离至少为两位置间距离。问，如果选择，使得总花费最少？

思路：

思路1：二分
一开始想的是这样二分：将船只按行驶距离和花费排序，找到第一个行驶距离大于间距的船只，答案+=此船花费。 但是可能后面行驶距离更长的船只花费还更少呢？
所以，从第一个行驶距离不小于间距的那条船开始，到后面的所有船都是满足要求的，最小花费为这些船中，花费的最小值。
所以，预先维护每个位置到最后一个位置中，花费的最小值f[i]。
二分加上第一个满足的位置的 f[i] 值就行了。

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m, a[N],b[N], f[N];
PII c[N];int main(){Ios;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);for(int i=2;i<=n;i++) b[i-1]=a[i]-a[i-1];n--;sort(b+1,b+n+1);for(int i=1;i<=m;i++) cin>>c[i].fi>>c[i].second;sort(c+1,c+m+1);f[m+1]=2e9;for(int i=m;i>=1;i--) f[i]=min(f[i+1],c[i].second);int flag=0;ll ans=0;for(int i=1;i<=n;i++){int l=1,r=m;while(l<r){int mid=l+r>>1;if(c[mid].first>=b[i]) r=mid;else l=mid+1;}if(c[l].first>=b[i]) ans+=f[l];else {flag=1;break;}}if(!flag) cout<<ans<<"\n";else cout<<"Impossible\n";}return 0;
}

思路2：贪心
如果正着来的话，每次都要把后面所有满足的都存起来。
正着不行倒着来。

将两个数组都从大到小排序。
设置一个指针，将满足比当前位置大的船的价值都存到优先队列中。
每次取队首元素就行了。

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m, a[N],b[N], f[N];
PII c[N];int main(){Ios;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);for(int i=2;i<=n;i++) b[i-1]=a[i]-a[i-1];n--;sort(b+1,b+n+1,greater<int>());for(int i=1;i<=m;i++) cin>>c[i].fi>>c[i].second;sort(c+1,c+m+1,greater<PII>());priority_queue<int,vector<int>,greater<int> > que;int flag=0;ll ans=0;int idx=1;for(int i=1;i<=n;i++){while(idx<=m&&c[idx].first>=b[i]) que.push(c[idx].second),idx++;if(!que.size()){flag=1;break;}else ans+=que.top();}if(!flag) cout<<ans<<"\n";else cout<<"Impossible\n";}return 0;
}

---

---

Codeforces Round #750 (Div. 2)

---

A.Luntik and Concerts（思维）

思路：

一共a*1+b*2+c*3个，分成两份。判断其模2结果。

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m;int main(){cin>>T;while(T--){int a,b,c;cin>>a>>b>>c;ll x=a+b*2+c*3;if(x%2==0) cout<<0<<endl;else cout<<1<<endl;} return 0;
}

---

B.Luntik and Subsequences（组合）

题意：

一个长度为 n 的数列，元素总和为 sum。
问这个数列中有多少子序列，其元素总和为sum-1?（子序列（集合）可以为空）

思路：

子序列总和为数列全部元素总和 -1，那么说明只有一个 元素1 没在子序列中。
但是，如果有元素0的话，可以选也可以不选。

设元素1出现了x次，元素0出现了y次。
那么，留下的那个元素1有x种策略。选择的0有2^y种策略。
所以，满足的序列个数为：$x\ast 2^y$。

需要注意的是，$2^y$，不要用左移运算！！
左移运算需要满足在 int 范围内，超过范围就会溢出为0了。。
所以左移运算只能在 y<31 的情况下使用。
两个月之后更~
左移运算超过int范围也是可以的，只不过要把前面的数字类型换成long long，得出的答案也是 long long 了。
像这样：cout << (1ll << 42);

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m, a[N];int main(){cin>>T;while(T--){cin>>n;int cnt1=0,cnt2=0;ll sum=0;for(int i=1;i<=n;i++){int x;cin>>x;if(x==0) cnt1++;if(x==1) cnt2++;sum+=x;}cout<<(ll)(cnt2*(ll)pow(2,cnt1))<<endl;}return 0;
}

---

C. Grandma Capa Knits a Scarf（模拟）

题意：

对于一个字符串，问最少执行下面操作多少次，能够将该字符串变成回文串？如果不可，输出-1。
操作：选择一种字符，删除若干个。

思路：

从两端往中间走，找到第一对不同的两个字符。
那么，这两种字符肯定要删除一个。
所以，两种情况讨论，取最优答案。

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m;
char a[N];int main(){Ios;cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int l=1,r=n;int tl,tr,ff=0;for(int i=1;i<=n/2;i++){if(a[l]!=a[r]){tl=l,tr=r;ff=1;break;}l++,r--;}if(!ff){cout<<0<<endl;continue;}char c=a[tl],d=a[tr];int lll=tl,rr=tr;int flag=0;int cnt=0;while(tl<tr){if(a[tl]!=a[tr]){if(a[tl]==c) tl++,cnt++;else if(a[tr]==c) tr--,cnt++;else{flag=1;break;}}if(a[tl]==a[tr]) tl++,tr--;}int ans=1e9;if(!flag) ans=min(ans,cnt);cnt=0;flag=0;tl=lll,tr=rr;while(tl<tr){if(a[tl]!=a[tr]){if(a[tl]==d) tl++,cnt++;else if(a[tr]==d) tr--,cnt++;else{flag=1;break;}}if(a[tl]==a[tr]) tl++,tr--;}if(!flag) ans=min(ans,cnt);if(ans!=1e9) cout<<ans<<endl;else cout<<-1<<endl;}return 0;
}

---

D. Vupsen, Pupsen and 0（构造，思维）

题意：

给定长度为 n 的数组 a。$(10^4\le ai\le 10^4,ai\ne 0)$
问，能否构造一个数组 b，使得 ai*bi 总和为 0，并且满足 $|bi|总和\le 1e9，bi\ne 0$。

思路：

设数组a：a b c d e f …

对于 n 为偶数：
那么为了使得 $ai\ast bi$ 总和为 0，可以两两配对，让这两两相加就 0。总和自然也为 0。
如何构造让这两两相加为 0 呢？对于 $相邻位置元素a,b$，可以构造第一个为 $b$，第二个为 $-a$。
$a\ast b+b\ast (-a)=0$。

对于 n 为奇数：
那么就先让前 $n-3$ 个数，肯定为偶数个，两两配对，使其总和为0。
然后构造让最后剩下的 3 个相乘总和为 0。
对于最后三个数 $x,y,z$，可以构造 $-z,-z,x+y$。
$x\ast (-z)+y\ast (-z)+z\ast (x+y)=0$。
但是，b 数组中元素不能为 0，所以要选择两个相加不为 0 的数充当 $x+y$。

Code：

const int N = 200010;
int T, n, m, a[N];int main(){Ios;cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];if(n%2==0){for(int i=1;i<=n;i++){if(i%2) cout<<a[i+1]<<" ";else cout<<-a[i-1]<<" ";}}else{for(int i=1;i<=n-3;i++){if(i%2) cout<<a[i+1]<<" ";else cout<<-a[i-1]<<" ";}int x=a[n-2],y=a[n-1],z=a[n];if(x+y!=0) cout<<-z<<" "<<-z<<" "<<x+y;else if(x+z!=0) cout<<-y<<" "<<x+z<<" "<<-y;else cout<<y+z<<" "<<-x<<" "<<-x;}cout<<endl;}return 0;
}

---

今天是1024哇~