A. Lunar New Year and Cross Counting
题意：
计算给定的数据中满足以下图形的
X.X
.X.
X.X题解：模拟
#include <bits/stdc++.h>
using namespace std;
int n,sum;
char s[1000][1000];
inline bool check(int x,int y){
if(s[x][y] == 'X' && s[x-1][y-1] == 'X' && s[x-1][y+1] == 'X' && s[x+1][y-1] == 'X' && s[x+1][y+1] == 'X') return true;
else return false;
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
scanf("%s",s[i]+1);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
if(check(i,j))
sum++;
printf("%d\n",sum);
return 0;
} B. Lunar New Year and Food Ordering
题意：
一共有n盘菜，每盘菜的数量为$a_i$,价格为$c_i$,一共有M个客人每个客人会要编号为$t_i$的菜$d_i$盘,如果菜品的盘数不够，他就会在剩下的菜品中选择最便宜的买。如果最后他买到的菜品不够$d_i$盘，那么他就不会给钱。否则的话他会支付相应的金额。
题解：
用set记录菜品的分量和价格，然后排序，额外用个数组记录每样菜品的价格和数量。最后一个一个更新。计算答案。需要注意的是无论如何都要同时更新数组和set
#include <bits/stdc++.h>
const int MAXN = 200000;
using namespace std;
long long n,m;
long long sum,sum1;
long long a[MAXN],c[MAXN];
struct node{
long long id,w,c;
friend bool operator < (const node &A,const node &B){
if(A.c == B.c) return A.id < B.id;
else return A.c < B.c;
}
};
set<node>S;
queue<node>Q;
inline void init()
{
scanf("%lld %lld",&n,&m);
for(int i = 1;i <= n;i++)
scanf("%lld",&a[i]);
for(int i = 1;i <= n;i++)
scanf("%lld",&c[i]);
for(int i = 1;i <= n;i++)
S.insert((node){i,a[i],c[i]});
}
int main()
{
init();
long long t,d;
for(int i = 1;i <= m;i++)
{
scanf("%lld %lld",&t,&d);
sum = 0;
if(a[t] >= d){
sum += d*c[t];
a[t] -= d;
S.erase(S.find((node){t,0,c[t]}));
S.insert((node){t,a[t],c[t]});
}
else {
long long tmp = 0;
tmp += a[t] * c[t];
d -= a[t];
if(a[t]) S.erase(S.find((node){t,0,c[t]}));
a[t] = 0;
for(auto it = S.begin();it != S.end();it++){
if(it->w > d){
tmp += d * it->c;
int id = it->id,w = it->w,c = it->c;
a[it->id] -= d;
S.erase(it);
S.insert((node){id,w-d,c});
it = S.find((node){id,w-d,c});
d = 0;
break;
}else{
tmp += it->c * it->w;
a[it->id] = 0;
d -= it->w;
Q.push(*it);
}
}
if(d == 0){
sum += tmp;
}
while(!Q.empty()){
auto it = Q.front();Q.pop();
S.erase(it);
}
}
printf("%lld\n",sum);
}
return 0;
}C. Lunar New Year and Number Division
题意：
将n个数字两两分组，使得最后的分组和的平方最大。
题解：
显然排序以后$$\large \sum_{i=1}^{\frac{n}{2}}(a_i+a_{n-i+1})^{2}$$
这样组合会使得和最小
#include <bits/stdc++.h>
const int MAXN = 300005;
using namespace std;
int n;
long long sum,d[MAXN];
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
scanf("%lld",&d[i]);
sort(d+1,d+n+1);
for(int i = 1;i <= n / 2;i++){
sum += (d[i]+d[n-i+1])*(d[i]+d[n-i+1]);
}
printf("%lld\n",sum);
return 0;
} D. Lunar New Year and a Wander
题意：
有一张N个点M条边的图，如果新到达一个点就将这个点按照访问顺序记录下来，需要求出一个使得记录字典序最小的顺序输出。
题解：
先将点1加入优先队列，将1从优先队列弹出来，然后将1的所有子节点加入优先队列，再弹出一个编号最小的点，将当前点的所有没有访问过的子节点加入优先队列。重复以上过程。
#include <bits/stdc++.h>
const int MAXN = 1000000;
using namespace std;
int n,m;
vector<int>E[MAXN];
priority_queue<int>Q;
bool vis[MAXN],inq[MAXN];
int main()
{
scanf("%d %d",&n,&m);
int u,v;
for(int i = 1;i <= m;i++){
scanf("%d %d",&u,&v);
E[u].push_back(v);
E[v].push_back(u);
}
Q.push(-1);vis[1] = true;
while(!Q.empty()){
int x = Q.top();Q.pop();
x = -x;
printf("%d ",x);
for(int i = 0;i < E[x].size();i++){
int v = E[x][i];
if(!vis[v]){
vis[v] = true;
Q.push(-v);
}
}
}
return 0;
}E. Lunar New Year and Red Envelopes
题意：
有n天时间，k个红包每个红包打开的时间范围是$s_i$至$t_i$打开这个红包会获得$w_i$个硬币，下次需要到$d_i$天之后才能开红包，Bob在每一天会在所有的红包中选择$w_i$最大的，如果有多个$w_i$最大的红包，就会选择$d_i$最大的打开，如果有多个$d_i$最大的红包那么会随机选择一个打开。而爱丽丝会阻止鲍勃获得金钱于是爱丽丝会选择一些天(小于等于M)使得在选择的那天鲍勃不能打开任何的红包。
题解：
假设我们已经计算出来每天要打开的红包
设dpi代表前i天在被妨碍j次的情况下能获得最小值。状态转移方程为:
对于求出来每天要打开的红包是哪个我采用三种不用的方法
第一种set
PS:因为set会去重所以我们排序关键词如果只有$w_i$和$d_i$那么我们会有一些红包没了。。。于是我额外加入$i$这个变量来比较使得不会有重复的元素出现。就不用multset。
#include <bits/stdc++.h>
const int MAXN = 100005;
using namespace std;
int n,m,k;
long long dp[MAXN][205],ans;
struct node{
int w,d,id;
friend bool operator < (const node &A,const node &B){
if(A.w == B.w && A.d == B.d) return A.id < B.id;
if(A.w == B.w) return A.d > B.d;
return A.w > B.w;
}
};
pair<int,int>inf[MAXN];
vector<int>L[MAXN],R[MAXN];
set<node>S;
int main()
{
scanf("%d %d %d",&n,&m,&k);
int s,t,d,w;
for(int i = 1;i <= k;i++){
scanf("%d %d %d %d",&s,&t,&d,&w);
L[s].push_back(i);R[t+1].push_back(i);
inf[i].first = w;inf[i].second = d;
}
memset(dp,63,sizeof(dp));
for(int i = 0;i <= m;i++)
dp[1][i] = 0;
for(int i = 1;i <= n + 1;i++)
{
for(int j = 0;j < L[i].size();j++)
{
int v = L[i][j];
S.insert((node){inf[v].first,inf[v].second,v});
}
for(int j = 0;j < R[i].size();j++){
int v = R[i][j];
S.erase(S.find((node){inf[v].first,inf[v].second,v}));
}
if(S.size()){
auto tmp = S.begin();
d = tmp->d;w = tmp->w;
for(int j = 0;j < m;j++){
dp[d+1][j] = min(dp[i][j]+w,dp[d+1][j]);
dp[i+1][j+1] = min(dp[i][j],dp[i+1][j+1]);
}
dp[d+1][m] = min(dp[i][m]+w,dp[d+1][m]);
}
else{
for(int j = 0;j <= m;j++)
dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
}
}
ans = LONG_LONG_MAX;
for(int i = 0;i <= m;i++)
ans = min(ans,dp[n+1][i]);
printf("%lld\n",ans);
return 0;
} 第二种：线段树
相当于对于区间$s_i$至$t_i$内的数如果小于$pair<w_i,d_i>$那么更新，否则不管。这显然就是一个线段树的基本操作。就是这种线段树有一个基本剪枝就是如果不能更新就返回。
#include <bits/stdc++.h>
const int MAXN = 400005;
#define lson o<<1,L,M
#define rson o<<1|1,M+1,R
using namespace std;
int n,m,k,ql,qr;
long long dp[100005][205],ans;
pair<int,int>P[MAXN],tmp,d[100005];
inline void update(int o,int L,int R){
if(P[o] >= tmp) return;
if(ql <= L && R <= qr){
P[o] = max(P[o],tmp);
return;
}
int M = L + R >> 1;
if(ql <= M) update(lson);
if(M < qr) update(rson);
}
inline void T_init(int o,int L,int R)
{
if(L == R){
d[L] = P[o];
if(d[L].second == 0) d[L].second = L;
return;
}
int M = L + R >> 1;
P[o<<1] = max(P[o<<1],P[o]);P[o<<1|1] = max(P[o<<1|1],P[o]);
T_init(lson);
T_init(rson);
}
inline void init()
{
scanf("%d %d %d",&n,&m,&k);
for(int i = 1;i <= k;i++){
scanf("%d %d %d %d",&ql,&qr,&tmp.second,&tmp.first);
update(1,1,n);
}
T_init(1,1,n);
}
int main()
{
init();
memset(dp,63,sizeof(dp));
for(int i = 0;i <= m;i++) dp[1][i] = 0;
for(int i = 1;i <= n;i++){
tmp = d[i];
for(int j = 0;j <= m;j++){
dp[tmp.second+1][j] = min(dp[tmp.second+1][j],dp[i][j]+tmp.first);
if(j != m) dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]);
}
}
ans = LONG_LONG_MAX;
for(int i = 0;i <= m;i++)
ans = min(ans,dp[n+1][i]);
printf("%lld\n",ans);
return 0;
} 第三种：ST表
相当于对于区间$s_i$至$t_i$内的数如果小于$pair<w_i,d_i>$那么更新，否则不管。第二种方法用的线段树维护的。
但是！！！！著名的大圣年前曾说过
如果题目是静态的（对于任意询问都在每一个修改操作之后），那么大概率存在某种数据结构能替代线段树--大圣
显然本题就是一个静态的而且询问在每一个操作之后。所以在大圣不抛弃不放弃的教导之后，我明白了我们原来的普通的ST表的更新操作
$$Max[j][i] = max(Max[j][i-1],Max[j+(1<<i-1)][i-1])$$
但是对于本题而言反过来也是成立的。
$$Max[j][i-1] = max(Max[j][i-1],Max[j][i])\\Max[j+(1<<i-1)][i-1] = max(Max[j+(1<<i-1)][i-1],Max[j][i])$$
于是只用先把标记打上去最后一次性全部压至叶子节点
#include <bits/stdc++.h>
const int MAXN = 100005,MAXD = 20;
using namespace std;
int n,m,k,d[MAXD+5];
long long dp[MAXN][205],ans;
pair<int,int>P[MAXN][MAXD+5],tmp;
inline void init()
{
scanf("%d %d %d",&n,&m,&k);
d[0] = 1;
for(int i = 1;i <= MAXD;i++) d[i] = d[i-1] << 1;
int s,t;
for(int i = 1;i <= k;i++)
{
scanf("%d %d %d %d",&s,&t,&tmp.second,&tmp.first);
int pos = 0;
while(d[pos+1] <= t - s + 1) pos++;
P[s][pos] = max(P[s][pos],tmp);
P[t-d[pos]+1][pos] = max(P[t-d[pos]+1][pos],tmp);
}
for(int i = MAXD;i >= 1;i--)
for(int j = 1;j + d[i] <= n + 1;j++)
{
P[j][i-1] = max(P[j][i-1],P[j][i]);
P[j+d[i-1]][i-1] = max(P[j+d[i-1]][i-1],P[j][i]);
}
for(int i = 1;i <= n;i++)
if(P[i][0].second == 0)
P[i][0].second = i;
}
int main()
{
init();
memset(dp,63,sizeof(dp));
for(int i = 0;i <= m;i++) dp[1][i] = 0;
for(int i = 1;i <= n;i++)
{
tmp = P[i][0];
for(int j = 0;j <= m;j++)
{
dp[tmp.second+1][j] = min(dp[i][j]+tmp.first,dp[tmp.second+1][j]);
if(j != m) dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]);
}
}
ans = LONG_LONG_MAX;
for(int i = 0;i <= m;i++)
ans = min(ans,dp[n+1][i]);
printf("%lld\n",ans);
}
