题目链接

T1 A

赛时思路：

对于每次求 \(s_{i}\) 时，对于剩下的 \(s\) 进行排序， 然后删除最大的， 最后找到第 \(pos\) 位输出字符即可。

时间复杂度：\(O_{\big(t \times (nlogn + nlogn)\big)}\)

code
#include 
using namespace std;int t, pos;
string s, sn;
struct node{int id;char c;
};inline bool cmp1(node x, node y){return (x.c - 'a') < (y.c - 'a');
}
inline bool cmp2(node x, node y){return x.id < y.id;
} int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);freopen("A.in", "r", stdin);freopen("A.out", "w", stdout);cin >> t;while(t--){cin >> s >> pos;int len = s.size();string sall = s; node str[10005];for(int i = 1;i <= len;i++){str[i].c = s[i - 1];}
//		for(int i = 1;i <= len;i++){
//			cout << str[i].c;
//		}while(len && sall.size() <= pos){for(int i = 1;i <= len;i++){str[i].id = i;}sort(str + 1, str + 1 + len, cmp1);
//			for(int i = 1;i <= len;i++){
//				cout << str[i].c;
//			} 
//			cout << endl;sort(str + 1, str + len, cmp2);for(int i = 1;i < len;i++){sall += str[i].c;}//			cout << "\n----------------------\n";len--;}
//		cout << sall;
//		cout << endl;
//		cout << "ans:";
//		cout << sall[pos];cout << sall[pos - 1];}return 0;
}
/*str:c->a->bi:1  2  3
next:2  3sort{str:c->b->ai:1  2  3
next:2     3
}str:c->a->bi:1  2  3
next:2  3
*/

预计得分：60（时间复杂度不优） 实际得分：10

T2 B

赛时思路:

暴力枚举。但是好像写错了， 样例都没过。

code
#include 
using namespace std;int t, n, m, minn = 1e9, maxx;int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);freopen("B.in", "r", stdin);freopen("B.out", "w", stdout);cin >> t;while(t--){cin >> n >> m;minn = 1e9, maxx = 0;int a[10005] = {}, b[10005] = {};for(int i = 1;i <= n;i++){cin >> a[i];}for(int i = 1;i <= m;i++){cin >> b[i];}for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){minn = min(minn, a[i] | b[j]);maxx = max(maxx, a[i] | b[j]);}}cout << minn << " " << maxx << "\n";} return 0;
}
预计得分：0

实际得分：0

T3 C

赛时思路:

如代码中的注释

code
#include 
using namespace std;int t, n, k;
struct node{int w, id;
}a[200005];
//id表示在原序列中是第几位
//w表示进行一次这个操作的费用 
inline bool cmp(node x, node y){if(x.w != y.w){return x.w < y.w;} else {return x.id > y.id;}}//优先按费用排序，因为题目要求字典序最高，第一位越高字典序越高
//其次按id排序，第一位相同，后面的越大字典序越大 int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//加速 
//	freopen("C.in", "r", stdin);
//	freopen("C.in", "w", stdout);cin >> t;while(t--){cin >> n;int b[200005] = {};for(int i = 1;i <= n;i++){a[i].id = i;a[i].w = 0;}//初始化 for(int i = 1;i <= n;i++){cin >> a[i].w;}//输入 a[n + 1].w = 1e9;//浪费格子 cin >> k;sort(a + 1, a + 1 + n, cmp);//排序 for(int i = 1;i <= n;i++){if(k % a[i].w > 0){continue;}//利益最大化，用不完就下一个 b[1] += k / a[i].w;b[a[i].id + 1] -= k / a[i].w;//差分，把1~a[i].id这个区间内的数全部加上k/a[i].w(就是可进行的操作数) k %= a[i].w;//用了之后要减去费用 }for(int i = 1;i <= n;i++){b[i] += b[i - 1];}//前缀和累加 for(int i = 1;i <= n;i++){cout << b[i] << " ";}cout << "\n";}return 0;
}
预计得分：100

实际得分：100

T5 E

赛时思路：

通过样例找规律骗分。

发现一个规律：

如果数组中每一位都相等， 则答案为： \(n^2\)

code
#include 
using namespace std;int n, ans;
string s[10005];
bool flag = 1;int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);freopen("E.in", "r", stdin);freopen("E.out", "w", stdout);cin >> n;for(int i = 0;i < n;i++){cin >> s[i];if(i > 1 && s[i] != s[i - 1]){flag = 0;} }if(flag){cout << n * n;return 0;} else { ans = n;for(int i = 1;i <= n;i++){for(int j = 1;j <= n && i != j;j++){if((s[i].size() + s[j].size()) % 2 == 0){int sumi = 0;int sumj = 0;for(int k = 1;k <= n;k++){if(k <= n / 2){sumi += s[i][k] - '0';} else {sumj += s[i][k] - '0';}}if(sumi == sumj){ans++;}}}}}cout << ans;return 0;
}