int main() {
string s; cin >> s;
int x = s[6] - '0';
if(x % 2) cout << 1 << endl;
else cout << 0 << endl;
return 0;
}
思路:
依次枚举每个位置的后26位（包括自己）判断是否每个字母只出现一次，如果否，则继续往下走，否则就再把？填充进去。
代码：
int main() {
string s; cin >> s;
int flag = 0;
for(int i = 0, j = 0; i < s.size(); i++) {
if(s[i] != '?') w[s[i] - 'A']++;
while(w[s[i]-'A'] > 1) w[s[j++]-'A']--;
if(i - j == 25) {
flag = 1;
for(int x = j; x <= i; x++) {
if(s[x] == '?') {
for(int k = 0; k < 26; k++) {
if(w[k]==0) {
s[x] = (char)('A'+k);
w[k]++;
break;
}
}
}
}
break;
}
}
if(!flag) cout << -1 << endl;
else {
for(int i = 0; i < s.size(); i++) {
if(s[i] == '?') cout << 'A';
else cout << s[i];
}
cout << endl;
}
return 0;
}
思路：
先把个数为1的平均分给两个人，个数为2的对结果不构成影响，再去找个数大于2的，只需要把其中一个给个数少的A，其他的给个数多一个的B就行了。
代码：
int main() {
int n = read();
for(int i = 0; i < n; i++) {
int x = read();
pos[x].push_back(i);
}
int cnt = 0;
for(int i = 1; i < N; i++)
if(pos[i].size() == 1)
cnt++;
string ans(n, 'B');
for(int i = 1, k = 0; i < N; i++) {
if(pos[i].size() == 1) {
k++;
if(k <= cnt / 2) ans[pos[i][0]] = 'A';
else ans[pos[i][0]] = 'B';
}
}
bool success = true;
if(cnt % 2) {
success = false;
for(int i = 1; i < N; i++) {
if(pos[i].size() > 2) {
ans[pos[i][0]] = 'A';
for(int j = 1; j < pos[i].size(); j++) ans[pos[i][j]] = 'B';
success = true;
break;
}
}
}
if(!success) cout << "NO" << endl;
else {
cout << "YES" << endl;
cout << ans << endl;
}
return 0;
}
另外附上比赛的时候的T3代码（只过了17个样例）：
int main() {
int n = read();
for(int i = 0; i < n; i++) {
w[i] = read();
cnt[w[i]]++;
pos[w[i]].push_back(i);
}
int k = 0;
for(int i = 1; i <= 100; i+=2) {
for(int j = 0; j < n; j++) {
if(cnt[w[j]] == i && !st[w[j]]) {
st[w[j]] = 1;
if(k) {
int t = pos[w[j]].size();
//cout << t << endl;
for(int tt = 0; tt < t - 1; tt++) dispute[pos[w[j]][tt]] = 1;
dispute[pos[w[j]][t-1]] = 2;
k = 0;
}else {
int t = pos[w[j]].size();//cout << t << endl;
for(int tt = 0; tt < t - 1; tt++) dispute[pos[w[j]][tt]] = 2;
dispute[pos[w[j]][t-1]] = 1;
k = 1;
}
// cout << k << endl;
}
}
}
if(k) {
for(int i = 2; i <= 100; i+=2) {
for(int j = 0; j < n; j++) {
if(cnt[w[j]] == i && !st[w[j]] && i != 2) {
st[w[j]] = 1;
if(k) {
int t = pos[w[j]].size();
//cout << t << endl;
for(int tt = 0; tt < t - 1; tt++) dispute[pos[w[j]][tt]] = 1;
dispute[pos[w[j]][t-1]] = 2;
k = 0;
break;
}else {
int t = pos[w[j]].size();//cout << t << endl;
for(int tt = 0; tt < t - 1; tt++) dispute[pos[w[j]][tt]] = 2;
dispute[pos[w[j]][t-1]] = 1;
k = 1;
}
// cout << k << endl;
}
}
if(!k) break;
}
}
if(k) cout << "NO" << endl;
else {
cout << "YES" << endl;
for(int i = 0; i < n; i++) {
if(!st[w[i]]) cout << "A";
else if(dispute[i] == 1) cout << 'A';
else cout << 'B';
}
}
return 0;
}