The 2020 ICPC Asia Shenyang Regional Programming Contest Northeastern University（SMU 2024 ICPC 网络赛选拔赛2）
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
思路
队友写的，大致就是运用数论的同余关系。
代码
#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;
}