中国大学生程序设计竞赛（秦皇岛）正式赛东北大学秦皇岛分校（SMU Autumn 2024 Team Round 1）
Problem A. 贵校是构造王国吗 I
思路
官方题解很清晰明了。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
const int N=1e6+3;
void solve() {
int n,k;
cin>>n>>k;
int dq=1;
vector<PII>ans;
set<PII>st;
ans.push_back({1,1});
st.insert({1,1});
dq++;
int ls=1;
for (int i = 2; i <=n ; ++i) {
ans.push_back({i,ls});
st.insert({i,ls});
dq++;
ls++;
ans.push_back({i,ls});
st.insert({i,ls});
dq++;
}
ans.push_back({1,n});
st.insert({1,n});
dq++;
if(dq>k){
for(auto [x,y]:ans){
cout<<x<<' '<<y<<endl;
}
return ;
}
else{
for (int i = 1; i <=n ; ++i) {
for (int j = 1; j <=n ; ++j) {
if(st.count({i,j})==0){
ans.push_back({i,j});
if(ans.size()==k){
for(auto [x,y]:ans){
cout<<x<<' '<<y<<endl;
}
return ;
}
}
}
}
}
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
Problem D. 茶和咖啡
思路
和题解类似。不过我们是用线段树维护前缀最小的物品。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define INF INT_MAX
#define N 200010
#define lc p<<1
#define rc p<<1|1
int n, w[N];
int a[N],b[N];
struct node{
int l,r;
PII mi;
}tr[N<<2],tr1[N<<2];
void push_up(int p){
tr[p].mi=min(tr[lc].mi,tr[rc].mi);
}
void build(int p,int l,int r){
tr[p]={l,r,{0,0}};
if(l==r){tr[p]={l,r,{w[l]-b[l],l}};return;}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(p);
}
void update(int p,int x,int k){
if(tr[p].l==x and tr[p].r==x){
tr[p].mi.first+=k;
return;
}
int mid=tr[p].l+tr[p].r>>1;
if(x<=mid)update(lc,x,k);
if(x>mid)update(rc,x,k);
push_up(p);
}
PII query(int p,int x,int y){
if(x<=tr[p].l and tr[p].r<=y){
return tr[p].mi;
}
int mid=tr[p].l+tr[p].r>>1;
PII sum={INF,0};
if(x<=mid){
sum=min(sum, query(lc,x,y));
}
if(y>mid){
sum=min( query(rc,x,y),sum);
}
return sum;
}
void push_up1(int p){
tr1[p].mi=min(tr1[lc].mi,tr1[rc].mi);
}
void build1(int p,int l,int r){
tr1[p]={l,r,{0,0}};
if(l==r){tr1[p]={l,r,{w[l]-b[l],l}};return;}
int mid=(l+r)>>1;
build1(lc,l,mid);
build1(rc,mid+1,r);
push_up1(p);
}
void update1(int p,int x,int k){
if(tr1[p].l==x and tr1[p].r==x){
tr1[p].mi.first+=k;
return;
}
int mid=tr1[p].l+tr1[p].r>>1;
if(x<=mid)update1(lc,x,k);
if(x>mid)update1(rc,x,k);
push_up1(p);
}
PII query1(int p,int x,int y){
if(y==0)return {INF,0};
if(x<=tr1[p].l and tr1[p].r<=y){
return tr1[p].mi;
}
int mid=tr1[p].l+tr1[p].r>>1;
PII sum={INT_MAX,0};
if(x<=mid){
sum=min(sum, query1(lc,x,y));
}
if(y>mid){
sum=min( query1(rc,x,y),sum);
}
return sum;
}
void solve(){
int q;
cin>>n>>q;
for (int i = 1; i <=n ; ++i) {
cin>>w[i];
a[i]=b[i]=0;
}
build(1,1,n);
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
a[x]+=y;
}
b[n+1]=0;
for(int i=n;i>=1;i--){
b[i]=a[i]+b[i+1];
}
build1(1,1,n);
int pos=n,s=0;
int ans=0;
for(int i=1;i<=n;i++){
auto[mn,pp]=query1(1,1,pos);
mn+=s;
if(pos<n){
auto[mn1,pp1]=query(1,pos+1,n);
if(mn1<mn){
mn=mn1;
pp=pp1;
}
}
if(pp<=pos){
pos=pp-1;
s=b[pp];
}
update(1,pp,INF);
update1(1,pp,INF);
ans+=mn;
cout<<ans<<' ';
}cout<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
Problem G. 最大路径
思路
懒得写了，题解写得很清楚，赞
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
const int N=1e6+3;
void solve() {
int n,m;
cin>>n>>m;
int ans=0;
vector<int>a(n),b(m);
for (int i = 0; i <n ; ++i) {
cin>>a[i];
}
for (int i = 0; i <m ; ++i) {
cin>>b[i];
}
for (int i = 1; i <n ; ++i) {
ans+=abs(a[i-1]-a[i]);
}
for (int i = 1; i <m ; ++i) {
ans+=abs(b[i-1]-b[i]);
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
Problem J. 维克多词典
思路
子集 DP。
单词长度很小，可以考虑状压DP求答案。
设 \(dp_S\) 为为学习完 S 的集合长度的单词的最小天数，转移的时候枚举每个 S 的子集即可。
代码
#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 = 1e4 + 10;
int a[100];
vector<int>q;
PII S[N];
vector<int>g[20];
void solve() {
int n, w;
cin >> n >> w;
int t = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (!a[x]) {
t++;
q.push_back(x);
}
a[x]++;
}
for(int i=0;i<(1<<t);i++){
S[i]={1e9,1e9};
g[__builtin_popcount(i)].push_back(i);
}
S[0]={0,0};
for (int i = 0; i < t; ++i){
for(auto j:g[i]){
for(int k=0;k<t;k++){
if ((j >> k & 1)==0) {
PII x=S[j];
if(a[q[k]]+x.second<=w){
x.second+=a[q[k]];
}else{
x.first++;
x.second=a[q[k]];
}
S[j^(1<<k)]=min(S[j^(1<<k)],x);
}
}
}
}
cout<<S[(1<<t)-1].first+(S[(1<<t)-1].second>0)<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin>>t;
while (t--) {
solve();
}
return 0;
}