（EF给我干蒙了，有时间补吧……
A. Contest Start
题意：有n个人比赛，其中第一个在0开始，第二个在x，第i个在（i-1）*x开始，每个人在t时间后结束比赛，每个人的不满意度是他结束比赛时场上开始比赛且尚未完赛的人数，求总不满意度。
思路：t<x时ans为0，t==x时ans为n-1，t>x时我们可以得出在n足够大的时候，满足让一个人不满意的人应该是一个依次向后的排列（如图）。分类讨论初始长度k与n关系。
代码：
int main() { ios::sync_with_stdio(false); cin.tie(nullptr),cout.tie(nullptr); //IO cin>>t; while(t--) { ans=0; cin>>n>>m>>k; if(k<m)ans=0; else if(k==m)ans=n-1; else { ll kk=min(n-1,k/m); if(kk==n-1)ans=(n*(n-1))/2; else { if(n<kk+1)ans=(n*(n-1))/2; else ans=(kk*(kk+1))/2+kk*(n-kk-1); } } cout<<ans<<endl; } }
（然后发现我想多了，其实思路可以非常简单//XD
B. Love Song
题意：水。
代码：
View Code
int main() { ios::sync_with_stdio(false); cin.tie(nullptr),cout.tie(nullptr); //IO //cin>>t; //while(t--) { a[0]=0; cin>>n>>m; string s; cin>>s; rep(i,1,n) { if(i)a[i]=a[i-1]+s[i-1]-‘a‘+1; } rep(i,1,m) { ll l,r; cin>>l>>r; ans=a[r]-a[l-1]; cout<<ans<<endl; } } }
C. Stable Groups
题意：给定n个数和k，x两个正整数，现有n个分值为ai的学生，要求排列后相邻两个学生的差的绝对值不大于x，至多能在序列中插入k个任意分值的学生，最少能把原序列加上新的学生后（可不全加或不加）分为几个满足条件的子序列。
思路：我瞎搞的……数据应该比较水，算是个很好想的贪心，找到每个不满足条件的空缺处，找到此处最少需要几个新学生填补，然后升序填进去。
代码：
View Code
map<ll,ll>mp; int main() { ios::sync_with_stdio(false); cin.tie(nullptr),cout.tie(nullptr); //IO cin>>n>>k>>x; rep(i,1,n)cin>>a[i]; sort(a+1,a+1+n); rep(i,2,n) { if(a[i]-a[i-1]>x) { ll kk=(a[i]-a[i-1]-1)/x;//? ans++; if(!mp[kk])vis[++tt]=kk; mp[kk]++; } } ans++; sort(vis+1,vis+tt+1); rep(i,1,tt) { if(k>mp[vis[i]]*vis[i]) { ans-=mp[vis[i]]; k-=mp[vis[i]]*vis[i]; } else if(k==mp[vis[i]]*vis[i]) { ans-=mp[vis[i]]; k=0; i=tt+1; } else { ans-=k/vis[i]; k=0; i=tt+1; } } cout<<ans<<endl; }
D. PriceFixed
题意：要买n种商品，每种商品要买ai个，每种商品在购买过bi件任意商品后可以打五折，每件商品原价为2，最少需要多少钱。
思路：很明显单纯为了打折而去买多的商品至少需要1+1元，和直接买没区别，那就是直接贪心了。
代码：
View Code
bool cmp(node a,node b) { return a.b<b.b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr),cout.tie(nullptr); //IO cin>>n; rep(i,1,n) { cin>>c[i].a>>c[i].b; } sort(c+1,c+1+n,cmp); ll l=1,r=n; while(l<=r) { if(c[l].b<=cnt) { ans+=c[l].a; cnt+=c[l].a; l++; } else { ll minn=min(c[r].a,c[l].b-cnt); cnt+=minn; ans+=2*minn; c[r].a-=minn; if(c[r].a==0)r--; } } cout<<ans<<endl; }
/*
E. Game with Cards
看着感觉像dp，但搞不出来，结束看有人写的是线段树，有时间再补吧……
*/