温馨提示：打完 ABC 也要发 TJ。
完成补题 或者 参加 ABC 的，同步完成题解报告。 ——cls
题目大意：有 杯冰只因凌，每杯冰只因凌有 眼睛的味道（目の味） 看上去的味道 和美味度 ，你要吃掉两杯冰只因凌，编号分别为 和 （），这两杯冰只因凌的总美味度 计算方式如下：
求 的最大值。
实际上完全不用管那个 ，因为当 时，直接相加满足交换律；否则，两个数相等哪个除以 都没问题。
然后，因为 要最大，因此只要选择两种方案：最大的一组 不同的数，最大的一组 相同的数。取个 。
#include<bits/stdc++.h>
using namespace std;
struct Ic{
int f,s;
bool operator<(Ic b){
return s < b.s;
}
}ics[300005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
for(int i = 1;i <= n;i ++)
cin >> ics[i].f >> ics[i].s;
sort(ics + 1,ics + 1 + n);
if (ics[n].f != ics[n - 1].f)
cout << ics[n].s + ics[n-1].s;
else{
int ans = ics[n].s + ics[n - 1].s / 2;
int i = n - 1;
while(i >= 1 && ics[i].f == ics[n].f)i --;
cout << max(ans, i ? ics[n].s + ics[i].s : 0);
}
return 0;
}
这道题很多人挂了hhh
题目大意：给定一个字符矩阵，每次把至少有 个字符且每个字符相同的行、列的每个字符打上标记，结束时删去所有标记字符。重复直到没有可删去的行或列为止，输出剩余的字符数量。
我们统计每个行和列总字符数和每种字符的数量，每次查看并更新即可，最大数据时时间复杂度接近 ，一百多毫秒过了，ATCODER YES！
据说 wrc 也是这么写的，但是挂了淦。
#include<bits/stdc++.h>
using namespace std;
char c[2005][2005];
int linecnt[2005][30], linecnt2[2005];
int colcnt[2005][30], colcnt2[2005];
int tmpcnt[2005][30];
bool killl[2005], killc[2005];
int h,w,cnt;
int main() {
cin >> h >> w;
cnt = h * w;
while(getchar()!='\n');
for(int i = 1;i <= h;i ++){
linecnt2[i] = w;
for(int j = 1;j <= w;j ++)
c[i][j] = getchar(), linecnt[i][c[i][j] - 'a'] ++, colcnt[j][c[i][j] - 'a'] ++, colcnt2[j] = h;
//cout <<endl;
while(getchar() != '\n');
}
bool flag = true;
while(flag){
flag = false;
for(int i = 1;i <= w;i ++)
for(int j = 0;j < 26;j ++)
tmpcnt[i][j] = colcnt[i][j],tmpcnt[i][26] = colcnt2[i];
for(int i = 1;i <= h;i ++)
for(int j = 0;j < 26;j ++)
if(linecnt[i][j] == linecnt2[i] && linecnt2[i] >= 2 && !killl[i]){
cnt -= linecnt2[i];
linecnt2[i] = 0;
for(int k = 1;k <= w;k ++)
if(c[i][k] == j + 'a')
colcnt2[k] --,colcnt[k][j] --;
//cout << "Line Kill "<< i <<"Sub "<<linecnt2[i]<<endl;
killl[i] = true;;
flag = true;
}
for(int i = 1;i <= w;i ++)
for(int j = 0;j < 26;j ++)
if(tmpcnt[i][j] == tmpcnt[i][26] && tmpcnt[i][26] >= 2 && !killc[i]){
cnt -= colcnt2[i];
for(int k = 1;k <= h;k ++)
if(c[k][i] == j + 'a')
linecnt2[k] --,linecnt[k][j] --;
//cout << "Col Kill "<< i <<"Sub "<<colcnt2[i]<<endl;
killc[i] = true;
flag = true;
}
}
cout << cnt <<endl;
return 0;
}
这道题最高评 。
题目大意：你有 本书，每本书在读之前都要读 本书，分别是 ，求在读书本 之前要读哪些书。
拓扑排序模板，模板的不能再模板（因此也可以 DFS）。
#include<bits/stdc++.h>
using namespace std;
vector<int>fa[200005];
bool vis[200005];
int n;
void dfs(int now) {
if(vis[now])
return;
vis[now]=true;
for(int i = 0;i < fa[now].size();i ++)
dfs(fa[now][i]);
if(now != 1)
cout<<now<<" ";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
for (int i = 1;i <= n;i ++){
int x;
cin >> x;
while(x --) {
int child;
cin >> child;
fa[i].push_back(child);
}
}
dfs(1);
return 0;
}