The 2020 ICPC Asia Shenyang Regional Programming Contest Northeastern University（SMU 2024 ICPC 网络赛选拔赛2）
D. Journey to Un'Goro
思路
队友写得，没看。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int long long
#define PII pair<int,int>
#define endl '\n'
typedef long long ll;
const int N = 2e5;
vector<bitset<100000>>q;
map<int, int>hm;
vector<string>a;
int b[N];
void solve() {
int n;
cin >> n;
if (n <= 20) {
int mx = 0;
for (int i = 0; i < (1 << n); i++) {
int t = i;
string s = "";
int tt = 0;
for (int j = 0; j < n; j++) {
if (t & 1)s += 'r';
else s += 'b';
tt *= 2;
tt += t & 1;
t /= 2;
}
int mm = 0;
for (int j = 0; j < n; j++) {
b[j + 1] = b[j] + (s[j] == 'r');
}
for (int j = 0; j < n; j++) {
for (int k = j; k < n; k++) {
int ss = b[k + 1] - b[j];
if (ss & 1) {
mm++;
}
}
}
if (mm > mx) {
a.clear();
q.clear();
mx = mm;
a.push_back(s);
} else if (mm == mx) {
a.push_back(s);
}
}
cout << mx << endl;
sort(a.begin(), a.end());
for (int i = 0; i < a.size() && i < 100; i++) {
cout << a[i] << endl;
// cout<<i<<endl;
}
}else{
int mx=0;
if(n&1){
mx=((n+1)/2)*((n+1)/2);
}else{
mx=((n+1)/2)*((n+1)/2+1);
}
bitset<100000>s=1;
int p=((n+1)/2)-1;
q.push_back((s<<p));
s<<=p;
if((n&1)==0)q.push_back(s<<1);
s<<=1;
p++;
for(int i=0;i<p;i++){
if(q.size()>=100)break;
if(i==0){
s[i]=1;
}else if(i==1){
s[i]=1;
}else{
s[i]=1;
s[i-2]=0;
}
q.push_back(s);
}
s=1;
p++;
s<<=p;
for(int i=0;i<(1<<p);i++){
if(q.size()>=100)break;
int mm=0;
for (int j = 0; j < n; j++) {
b[j + 1] = b[j] + (s[j] == 1);
}
for (int j = 0; j < n; j++) {
for (int k = j; k < n; k++) {
int ss = b[k + 1] - b[j];
if (ss & 1) {
mm++;
}
}
}
if(mm==mx)q.push_back(s);
int f=1,pos=0;
while(f){
if(s[pos]==1){
f=1;
s[pos]=0;
}else{
s[pos]=1;
f=0;
}
pos++;
}
}
s=1;
p++;
s<<=p;
for(int i=0;i<(1<<p);i++){
if(q.size()>=100)break;
int mm=0;
for (int j = 0; j < n; j++) {
b[j + 1] = b[j] + (s[j] == 1);
}
for (int j = 0; j < n; j++) {
for (int k = j; k < n; k++) {
int ss = b[k + 1] - b[j];
if (ss & 1) {
mm++;
}
}
}
if(mm==mx)q.push_back(s);
int f=1,pos=0;
while(f){
if(s[pos]==1){
f=1;
s[pos]=0;
}else{
s[pos]=1;
f=0;
}
pos++;
}
}
cout<<mx<<endl;
for (int i = 0; i < q.size() && i < 100; i++) {
for(int j=n-1;j>=0;j--){
if(q[i][j]==1){
cout<<'r';
}else{
cout<<'b';
}
}
cout<<endl;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin>>t;
while (t--) {
solve();
}
return 0;
}
F. Kobolds and Catacombs
思路
将 \(a\) 排序后的数组设为 \(b\)，然后判断 \(a\) 和 \(b\) 中非递减序列在 \(a\) 中覆盖的区间，尽可能的分小即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int long long
#define PII pair<int,int>
#define endl '\n'
typedef long long ll;
vector<int>q;
map<int, int>hm;
void solve() {
int n;
cin >> n;
vector<int>a(n);
vector<int>st1(n), st2(n);
vector<int>b(n);
for (int i = 0; i < n ; ++i) {
cin >> a[i];
b[i] = a[i];
}
int ans = 0;
sort(b.begin(), b.end());
q = b;
q.erase(unique(q.begin(), q.end()), q.end());
for (int i = 0; i < q.size(); i++) {
hm[q[i]] = i;
}
int s = 0;
for (int i = 0; i < n ; ++i) {
int p = hm[a[i]];
st1[p]++;
if (st1[p] > st2[p]) {
s++;
} else {
s--;
}
p = hm[b[i]];
st2[p]++;
if (st1[p] < st2[p]) {
s++;
} else {
s--;
}
if (s == 0) {
ans++;
} else {
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin>>t;
while (t--) {
solve();
}
return 0;
}
G. The Witchwood
思路
倒序排序后取前 \(k\) 个的和即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int long long
#define PII pair<int,int>
#define endl '\n'
typedef long long ll;
void solve() {
int n,k;
cin>>n>>k;
vector<int>a(n);
for (int i = 0; i <n ; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end(),greater<int>());
int ans=0;
for (int i = 0; i <k ; ++i) {
ans+=a[i];
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
I. Rise of Shadows
思路
队友写的，大致就是运用数论的同余关系。
网上看到一篇不错的题解，贴一下 2020 icpc 沈阳 I - Rise of Shadows(思维) - limil - 博客园 (cnblogs.com)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int long long
#define LL __int128
#define PII pair<int,int>
#define endl '\n'
typedef long long ll;
const int N = 2e5;
vector<bitset<100000>>q;
map<int, int>hm;
vector<string>a;
int b[N];
void solve() {
int h,m,A;
cin >> h>>m>>A;
if(A*2+1>=h*m){
cout<<h*m<<endl;
return;
}
int gg=__gcd(h-1,h*m);
LL s1=((h-1)/gg);
LL s2=((h*m)/gg);
int ans=0;
ans+=(h*m)/s2*(A/gg*2+1);
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin>>t;
while (t--) {
solve();
}
return 0;
}
K.Scholomance Academy
思路
英文一大堆，其实就是让你找到临界点，然后求图中这样每个临界点构成的矩形的面积并。
好像队友写得有点复杂（？，不过A了就行，%%%。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int long long
#define double long double
#define LL __int128
#define PII pair<double,double>
#define PIC pair<int,char>
#define endl '\n'
typedef long long ll;
const int N = 1e6+10;
vector<PIC>q;
int b[N];
vector<PII>ans;
map<double,double>hm;
void solve() {
int n;
cin>>n;
double s1=0,s2=0;
for(int i=1;i<=n;i++){
char x;
int y;
cin>>x>>y;
q.push_back({y,x});
if(x=='+')s1+=1;
if(x=='-')s2+=1;
}
sort(q.begin(),q.end());
int s=0;
double s3=0,s4=0;
for(int i=0;i<q.size();i++){
char x=q[i].second;
if(s==q[i].first){
if(x=='+')s3+=1;
if(x=='-')s4+=1;
continue;
}
hm[(s2-s4)/s2]=max(hm[(s2-s4)/s2],(s1-s3)/s1);
if(x=='+')s3+=1;
if(x=='-')s4+=1;
s=q[i].first;
}
// cout<<s1<<s2<<s3<<s4<<endl;
hm[(s2-s4)/s2]=max(hm[(s2-s4)/s2],(s1-s3)/s1);
for(auto[u,v]:hm){
ans.push_back({u,v});
}
sort(ans.begin(),ans.end());
ans.push_back({1,1});
double sum=0;
for(int i=0;i<ans.size()-1;i++){
sum+=ans[i].second*(ans[i+1].first-ans[i].first);
}
cout<<fixed<<setprecision(10)<<sum<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin>>t;
while (t--) {
solve();
}
return 0;
}