2021-2022-1 ACM集训队每周程序设计竞赛（3）题解

题意：
$你有a个苹果和p个苹果片$
$1个苹果可以制作3个苹果片$
$2个苹果片可以制作1个苹果派$
$问一共可以制作多少个苹果派$
$0<=a,p<=100$
思路：
$模拟$
时间复杂度：$O1$

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define de(x) cout << x << "\n" 
#define sf(x) scanf("%lld",&x)
#define pll pair<int,int> 
#define re register int
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e6 + 10 , M = 2010 , mod = 1e9 + 7 ;signed main()
{int n , p ;cin >> n >> p ;p += 3 * n ;de(p/2) ;return 0;
}

题意：
$你决定写一本介绍好餐馆的书。$
$你想介绍的餐厅有N家:餐厅1，餐厅2，...餐厅n$
$1<=n<=100.$

$餐厅i在Si市，$
$你对每一家餐厅都有一个得分p$
$1<=p<=100$
$没有两家餐馆得分相同。$

$您要按以下顺序介绍餐厅:$
$餐厅按其城市名称的字典顺序排列。$
$如果同一个城市有多家餐厅，$
$则按得分降序排列。$

$按照书中介绍的顺序打印餐厅的编号。$
思路：
$结构体自定义排序$
时间复杂度：$Onlogn$

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define de(x) cout << x << "\n" 
#define sf(x) scanf("%lld",&x)
#define pll pair<int,int> 
#define re register int
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e6 + 10 , M = 2010 , mod = 1e9 + 7 ;struct ai{int id , score ; // 编号 ， 得分string city ; // 城市名称
}q[M] ;bool cmp(ai a , ai b)
{if(a.city == b.city) return a.score > b.score ;  // 城市字典序相等的时候按照得分大于(逆序)排序else return a.city < b.city ;    //  否则按照字典序小于(顺序)排序
}signed main()
{int n ;cin >> n ;fer(i,1,n){cin >> q[i].city >> q[i].score ;q[i].id = i ;}sort(q + 1 , q + 1 + n , cmp) ;fer(i,1,n) {cout << q[i].id << "\n" ;}return 0;
}

题意：
$我们有“开”和“关”状态的n个开关和m个灯泡。$
$开关编号为1到n，$
$灯泡编号为1到m。$

$灯泡i连接了ki个开关:开关si1，si2，...，和siki。$
$对于灯泡i连接的这些开关中如果打开的开关数量mod2等于p[i]，灯泡i会被点亮。$

$开关的“开”和“关”状态有多少种组合可以点亮所有灯泡？$
$1<=n,m<=10$
$1<=ki<=n$
$p[i]=0/1$
思路：
$考虑n的范围最大只有10$
$我们可以暴力枚举所有开关打开或者关闭的状态$

$考虑使用状态压缩来做$
$用一个二进制数来表示当前n个开关的打开状态$

$假设现在的二进制数是010101$
$0表示没选这个开关，1表示选了这个开关$
$选了1的开关即为第1个第3个第5个$

从 0 到 2 n − 1 ( n 个 1 ) 包含了所有的可能性 从0到2^n-1(n个1)包含了所有的可能性 从0到2n−1(n个1)包含了所有的可能性
时间复杂度： O 10 ∗ 10 ∗ 2 10 O10*10*2^{10} O10∗10∗210

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define de(x) cout << x << "\n" 
#define sf(x) scanf("%lld",&x)
#define pll pair<int,int> 
#define re register int
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e6 + 10 , M = 2010 , mod = 1e9 + 7 ;int n , m ; // n个开关 m个灯泡
vector<int> q[M] ;
int p[M] ;signed main()
{cin >> n >> m ;fer(i,1,m){int k ;sf(k) ;fer(j,1,k){int x ;sf(x) ;q[i].pb(x) ;}}fer(i,1,m) sf(p[i]) ;int res = 0 ;  // res 表示最后的答案for(int i = 0 ; i < 1 << n ; i ++)  // 枚举所有可能的二进制状态{bool st[11] = {0} ;             //  初始化所有开关都关闭for(int j = 0 ; j < n ; j ++)   //  判断哪些开关开了{// 如果i这个二进制数的第j位是1的话if(i >> j & 1) st[j+1] = 1 ;  // 开关编号从1开始  所以+1}int cnt = 0 ;  // cnt表示当前打开的灯泡数量for(int j = 1 ; j <= m ; j ++)  //  枚举所有灯泡  判断当前这个灯泡是否打开{int k = 0 ;         //  k表示当前这个灯泡有几个对应的开关打开for(int z = 0 ; z < q[j].size() ; z ++)  // 枚举这个灯泡的所有开关{if(st[q[j][z]]) k ++ ;   //  如果这个开关打开了 k ++}if(k % 2 == p[j]) cnt ++ ;  //   如果 k % 2 == p[j] 说明这个灯泡被打开了  cnt ++}if(cnt == m) res ++ ;  // 如果所有灯泡都打开了  res ++}cout << res << "\n" ;return 0;
}

题意：
$你的朋友送了你一个序列D$
$这个序列D上一共有n个珠宝$
$按照从左到右的顺序$
$每个珠宝都有它的价值w[i]$

$1<=n<=50$
$-1e7<=w[i]<=1e7$

$你可以对这些珠宝进行最多k次操作$
$1<=k<=100$

$每次操作你都可以$
$操作A：取出D中最左边的宝石，放在手中。当D为空时，不能执行此操作。$
$操作B：取出D中最右边的宝石，放在手中。当D为空时，不能执行此操作。$
$操作C：选择手中的任意一个宝石并将其插入D的左端。如果手中没有宝$$石，则无法执行此操作。$
$操作D：选择手中的任意一个宝石并将其插入D的右端。如果手中没有宝$$石，则无法执行此操作。$

$求执行完最多k次操作之后你手上有的珠宝的价值之和的最大值$
思路：
$注意到n的最大范围只有50，k最大只有100$
$那么可以枚举左边选了多少个,右边选了多少个$

$如果选的当中有负的价值,肯定要把最小的从手中删除$
$(负数越小绝对值越大)$
$前提是还有操作数可以用$

$如果手上的都是正价值,可以不用继续操作$
$更新一下当前答案即可$
时间复杂度： O n 3 l o g n On^3logn On3logn

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define de(x) cout << x << "\n" 
#define sf(x) scanf("%lld",&x)
#define pll pair<int,int> 
#define re register int
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e6 + 10 , M = 2010 , mod = 1e9 + 7 ;int n , k ;
int a[N] ;signed main()
{cin >> n >> k ;fer(i,1,n) sf(a[i]) ;int res = 0 ;  // 答案for(int i = 0 ; i <= n ; i ++)  //  左边选i个{for(int j = 0 ; j <= n ; j ++)  // 右边选j个{if(i + j > k) continue ;  // 如果操作数大于k了 就退出multiset<int> q ;  // 包含重复元素的set(set内元素从小到大自动排序)int s = 0 ;  // 这种选法的最大值// 左边选i个for(int l = 1 ; l <= i ; l ++){q.insert(a[l]) ; s += a[l] ;}// 右边选j个for(int r = n ; r >= n - j + 1 && r > i ; r --){q.insert(a[r]) ;s += a[r] ;}if(i + j < k)  // 如果操作数不够k个 , 剩下的操作用来删除  {int d = k - (i + j) ;  // 可以用来删除的操作数while(d)  // 只要 d > 0 就可以删{if(*q.begin() >= 0) break ;  // 如果最小的元素大于等于0  说明不用删除if(*q.begin() < 0)   //  反之删除{s -= *q.begin() ; q.erase(q.begin()) ;}d -- ;  }}res = max(res,s) ;  // 更新答案}}cout << res << "\n" ;return 0;
}

题意：
$有一条从西到东的无限长的街道，我们认为这是一条无限长的数轴$
$这条街上计划进行N项道路工程。$
$第i个道路工程在坐标Xi处阻段该点阻挡的时间从Si-0.5到Ti-0.5$
$也就是说在Si-0.5到Ti-0.5这段时间内Xi这个点不能通过$
$第i个人将在时间Di开始从坐标0,不断以速度1个单位每秒正向行走，到达阻段点时停止行走。$
$求出每个人将要走的距离$
$如果这个人走的过程中不会遇到阻断点$
$则输出-1$
$1<=N,Q<=2e5(200000)$
$0<=Si<Ti<=1e9(1000000000）$
$1<=Xi<=1e9$
$0<=D1<D2<D3<.......<Dq<=1e9$
思路：
$其实我们可以发现每个人到达每个点的时间是动态的$
$枚举每个人去求行走距离显然不行$

$但是每个阻挡点的阻挡时间是不变的$
$考虑从这上面做$

$在Si-0.5到Ti-0.5这段时间内Xi这个点不能通过$
$等价于在区间[Si,Ti-1]这段时间之内这个人必须不能经过这个点$
$否则答案就是Xi$

$假设这个人从0号点的出发时间为k$
$他到达Xi这个点的时间为Xi+k$
$如果Si<=Xi+k<=Ti-1$
$说明这个人最远只能到达Xi这个点$
$把式子变形一下即为$
$Si-Xi<=k<=Ti-Xi-1$

$所以我们可以预处理所有的[Si-Xi,Ti-Xi-1]这个区间$
$这个区间的权值为Xi$

$所以题目变成了$
$给你n个区间,每个区间都有一个权值$
$在给你q个询问$
$每个询问给你一个数$
$求这个数所在区间的最小权值$

$其实很明显是一个区间修改+单点最小值查询$
$可以裸线段树/平衡树+离散化Onlogn$
$代码长度可能至少100行这里不太推荐$

$这里推荐另外一种方法$
$二分+set动态维护$

$对区间按照权值大小从小到大排序$
$二分找到这个区间所有的人$
$更新这些人的答案在把这些人删掉$
$每个人最多只被遍历一次$
$可以做到时间复杂度为nlogn$
时间复杂度：$Onlogn$

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define de(x) cout << x << "\n" 
#define sf(x) scanf("%lld",&x)
#define pll pair<int,int> 
#define re register int
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e6 + 10 , M = 2010 , mod = 1e9 + 7 ;int n , t ;  //  n个阻断工程和t个人
struct ai{int l , r , x ;
}q[N] ;    //  保存区间及其权值
set<pll> se ;   // set里面放2个数 {到达0号点的的时间,编号}
int ans[N] ;  // 答案数组bool cmp(ai a , ai b)
{return a.x < b.x ;
}
// 按照Xi的权值大小从小到大排序signed main()
{cin >> n >> t ;fer(i,1,n){int l , r , x ;sf(l) , sf(r) , sf(x) ;q[i] = {l-x,r-x-1,x} ; }sort(q + 1 , q + 1 + n , cmp) ;fer(i,1,t){int x ;sf(x) ;se.insert({x,i}) ;  // {这个人到达0号点的的时间,编号}}fer(i,1,t) ans[i] = -1 ;fer(i,1,n){int l = q[i].l , r = q[i].r , x = q[i].x ;while(se.size())  // 只要set里面还有数{auto it = se.lower_bound({l,-2e9}) ;// 找到第一个大于等于l这个数if(it == se.end()) break ;  // 如果它不存在 就退出// stl的所有容器end() 指向一个不存在的数  自动处理边界问题if(it -> first > r) break ; //  如果这个数不在[l,r]这个区间之内，也退出 ans[it -> second] = x ;  // it -> second 表示这个人的编号se.erase(it) ;  // 删除// set的操作基于平衡树 单次操作logn}}// 边遍历边删除 每个数只被遍历一次 故时间复杂度为nlognfer(i,1,t) cout << ans[i] << "\n" ;return 0;
}

题意：
$有一只青蛙，有0,1,\cdots ,N-1个荷叶。每个荷叶上有权值si。$
$你现在在0这个荷叶上$

$操作1$
$选定任意的2个正整数A,B，初始分数为0。$

$假设当前位置为x：$

$操作2$
$你的坐标移动到x+A这个位置上，并且y=x+A$
$如果y=N-1，游戏结束。$
$如果y\ne N-1，但是y这个荷叶存在，那么分数增加si，并且这片荷叶消失。$
$如果y\ne N-1，但是y这个荷叶不存在，那么分数减去10的100次方，游戏结$$束。$

$操作3$
$你的坐标移动到x-B这个位置上，并且y=x-B$
$如果y=N-1，游戏结束。$
$如果y\ne N-1，但是y这个荷叶存在，那么分数增加si，并且这片荷叶消失。$
$如果y\ne N-1，但是y这个荷叶不存在，那么分数减去10的100次方，游戏结$$束。$

$然后不断重复2和3操作$

$问选定最优的A、B的情况下，得到的最高分数为多少？$
$1<=n<=1e5(100000)$
$-1e9<=si<=1e9(1后面9个0）$
$s0=sn-1=0$
思路：
$考虑，选定了A、B后，青蛙的行走路线为：$
$0,A,A-B,A+(A-B),2(A-B),\cdots ,K(A-B),A+K(A-B)$

$令C=A-B：$
$0,A,C,A+C,2C,\cdots ,KC,A+KC$
$显然有：A+KC=N-1：$

$将A=N-1-KC带入上式$
$0,N-1-KC,C,N-1-(K-1)C,2C,\cdots ,KC,N-1$

$那么当K、C确定的时候，行走路线就已经确定。$
$并且有一个限制条件为KC<N，那么显然枚举K、C是O(nlogn)的。$

$并且我们发现，当我们固定C，递增K的时候，行走路线的变化是这样的：$
$0,N-1$
$0,N-1-C,C,N-1$
$0,N-1-2C,C,n-1-C,2C,N-1$

$每次增加的是N-1-KC和KC，这两个点，只需要加上就好了$
$并且要注意判断是否走到重复的点上了。$
时间复杂度：$Onlogn$

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define de(x) cout << x << "\n" 
#define sf(x) scanf("%lld",&x)
#define pll pair<int,int> 
#define re register int
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e5 + 10 , M = 2010 , mod = 1e9 + 7 ;int n ;
int s[N] ;
int used[N] ;signed main()
{cin >> n ;fer(i,0,n-1) sf(s[i]) ;int res = 0 ;for(int c = 1 ; c <= n ; c ++){int ans = 0 ;for(int k = 1 ; k * c < n ; k ++){int a = k * c;int b = n - 1 - k * c;int A = b, B = b - c;if (A <= 0 || B <= 0) break; if (a < 0 || a >= n || b < 0 || b >= n || a == b) break; if (used[a] == c || used[b] == c) {break;}used[a] = c;used[b] = c;ans += s[a];ans += s[b];res = max(res, ans);}}cout << res << "\n" ;return 0;
}