Codeforces Round 294 (Div. 2)

C题：有n个老师，m个学生，a方案是1老师和2学生，b方案是2老师和1学生，求最多可以成功达成多少套方案？

Sol：wa了一发贪心，样例怎么全过了？从纯数学的角度去看，就是线性规划，只不过由于参数不确定需要分类讨论，我们只需要设x套a，y套b，求x+y的最大值（在两个总人数的约束条件下。

1
2
3
4
5
6
7
void solve(){
	cin>>n>>m;
	if(m<n)swap(n,m);
	if(m>2*n)cout<<n<<endl;
	else cout<<(n+m)/3<<endl;
	//cout<<ad+tmp<<endl;
}

考虑到数据范围很小，官方正解是直接暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
#endif
 
    scanf("%d%d", &n, &m);
 
    for (int i = 0; i <= n; i++) {
        int cur = i;
        int leftn = n - i;
        int leftm = m - 2 * i;
 
        if (leftm >= 0) {
            cur += min(leftm, leftn / 2);
            ans = max(ans, cur);
        }
    }
 
    printf("%d\n", ans);
    
    return 0;
}

D：题意：给定一个字符串s，字符集有小写字母，每个小写字母有权值，求有多少个子串满足子串的首尾字母相等并且子串的f_权值为0.

f权值的定义是对于一个子串，去除首字母和尾字母的权值和。

Sol：首先预处理每个字母在哪些位置集合。先考虑简单的问题，假如就是子串的所有字母权值和，我们只需要在同一个字母的位置集合里查询前面有多少位置的前缀和等于这个位置就可以了。

  • 但现在需要偏移位置，推前缀和式子发现需要统计的是上一个位置的前缀和的个数，加进去的这个位置的前缀和，0位置的贡献在第一轮被加进去了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve(){
     map<char,int>mp;
     for(int i=1;i<=26;i++)cin>>mp['a'+i-1];
     string s;cin>>s;n=s.size();
	 s=" "+s;
	map<char,vector<int>>pos;
	 vector<int>pre(n+2,0);
	 for(int i=1;i<=n;i++){
	 	pre[i]=pre[i-1]+mp[s[i]];
	 	pos[s[i]].push_back(i);
	 }
	 int ans=0;
	 for(auto [x,y]:pos){
	 	map<int,int>tmp;
	 	for(auto u:y){
	 		ans+=tmp[pre[u-1]];
	 		tmp[pre[u]]++;
	 	}
	 }
	 cout<<ans<<endl;
	
	 
}

E；详情见lca专题