题集链接；
官方题解；
目录：
OP
标准的新生赛，所以补得比较快~
下次出题的时候结构可以参考一下这场，难度分布还比较适用；
A 小贪一手
贪心
思路
出于取模的性质，我们可以直接构造~
由于保证了解一定存在，也不需要担心无解的问题；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
int x,y,n;
while(t--)
{
scanf("%d%d%d",&x,&y,&n);
int bas=n/x*x+y;
if(bas>n)bas-=x;
printf("%d\n",bas);
}
return 0;
}
B A+B Problem (very easy)
模拟，字符串处理
思路
注意：题目中输入的-为英文的连字符，并非数学的减号；
先处理出所有合法数字的字符串对整型的映射，再在每次+或字符串结束时分割字符串，映射到数字并计算；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string, int> mp;
string bas[100] = {};
int main()
{
mp["zero"] = 0;bas[0]="zero";
mp["one"] = 1;bas[1]="one";
mp["two"] = 2;bas[2]="two";
mp["three"] = 3;bas[3]="three";
mp["four"] = 4;bas[4]="four";
mp["five"] = 5;bas[5]="five";
mp["six"] = 6;bas[6]="six";
mp["seven"] = 7;bas[7]="seven";
mp["eight"] = 8;bas[8]="eight";
mp["nine"] = 9;bas[9]="nine";
mp["ten"] = 10;
mp["eleven"] = 11;
mp["twelve"] = 12;
mp["thirteen"] = 13;
mp["fourteen"] = 14;
mp["fifteen"] = 15;
mp["sixteen"] = 16;
mp["seventeen"] = 17;
mp["eighteen"] = 18;
mp["nineteen"] = 19;
mp["twenty"] = 20;bas[20]="twenty";
mp["thirty"] = 30;bas[30]="thirty";
mp["forty"] = 40;bas[40]="forty";
mp["fifty"] = 50;bas[50]="fifty";
mp["sixty"] = 60;bas[60]="sixty";
mp["seventy"] = 70;bas[70]="seventy";
mp["eighty"] = 80;bas[80]="eighty";
mp["ninety"] = 90;bas[90]="ninety";
for (int i = 21; i <= 99; i++)
{
if (bas[i].length() <= 1)
{
bas[i] = bas[i / 10 * 10] + '-' + bas[i % 10];
mp[bas[i]] = i;
}
}
int t;
string gt;
cin >> t;
while (t--)
{
cin >> gt;
int p = 0;
int ans = 0;
for (int i=0;; i++)
{
if (gt[i] == '+' || !gt[i])
{
ans += mp[gt.substr(p, i - p)];
p = i + 1;
//printf("%d ", ans);
if(!gt[i]) break;
}
}
cout << ans << endl;
}
return 0;
}
C Alice and Bob
博弈论
思路
内容已补全
由于每次最大拿取量的限制，对于偶数m粒棋子，每一轮（各操作一次）的后手（与全局的先后手无关）可以控制两人操作完只剩 m ? 1 ? ? m / 2 ? m-1-\lceil m/2\rceil m?1??m/2? 粒（对于奇数m粒棋子后手无法控制）；
由于最后一轮完成后剩余0枚，我们可以解得上一个关键点为2，由2推出再上一个关键点为6……以此类推就会发现关键点的分布规律；
对于初始棋子数，如果恰好为关键点，则可以保证后手（全局的）必胜，否则先手者可以使棋子点数到达关键点，此时后手则必败了（可以认为全局先手第一次操作后到达关键点，此后全局后手变为回合先手，全局先手可以控制总棋子数到达关键点）；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>ok;
int main()
{
for(int i=2;i<=1000;i=i*2+2)
{
ok.push_back(i);
}
//cout<<ok[ok.size()-1];
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int f=0;
for(int i=0;i<ok.size()&&!f;i++)
{
if(n<ok[i])break;
else
{
if(n==ok[i])f=1;
}
}
if(f)printf("YES\n");
else printf("NO\n");
}
return 0;
}
D 进化
模拟，搜索，贪心
思路
所有运算项均为正数；
对于所有乘法项，显然乘法项越后计算结果越大；
我们可以将运算项视为不可通行块，找到当前区域边界上的所有运算项，将加法项直接计算，如果没有加法项，则选择倍率最低的乘法项运算；
运算项运算后便认为是可通行块，循环以上步骤，直到当前边界上没有新的运算块；
由于数据很小，我们可以放心大胆地多次bfs；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> mp[10][10]; // type,num//-1->no,0->ok,1->add,2->mut
pair<int, int> tmp[70];
bool rch[10][10];
int di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
int n, m;
int ctmp = 0;
void bfs(int x, int y)
{
queue<pair<int, int>> que;
if (!mp[x][y].first)
que.push({x, y}), rch[x][y] = 1;
else if (mp[x][y].first > 0)
{
tmp[ctmp++] = {x, y};
}
while (!que.empty())
{
int nowi = que.front().first, nowj = que.front().second;
que.pop();
for (int k = 0; k < 4; k++)
{
int nni = nowi + di[k], nnj = nowj + dj[k];
if (nni >= 1 && nni <= n && nnj >= 1 && nnj <= m)
{
if (!mp[nni][nnj].first && !rch[nni][nnj])
que.push({nni, nnj}), rch[nni][nnj] = 1;
else if (mp[nni][nnj].first > 0 && !rch[nni][nnj])
tmp[ctmp++] = {nni, nnj}, rch[nni][nnj] = 1;
}
}
}
}
int main()
{
int k, ni, nj, tx, ty, t, v;
cin >> n >> m;
string g;
for (int i = 1; i <= n; i++)
{
cin >> g;
for (int j = 0; j < m; j++)
{
mp[i][j + 1].first = (g[j] == '#') ? -1 : 0;
if (g[j] == 'S')
ni = i, nj = j + 1;
}
}
cin >> k;
for (int i = 1; i <= k; i++)
{
scanf("%d%d%d%d", &tx, &ty, &t, &v);
mp[tx][ty] = {t, v};
}
ll ans = 1;
while (1)
{
ctmp = 0;
memset(tmp, 0, sizeof tmp);
memset(rch, 0, sizeof rch);
bfs(ni, nj);
if (!ctmp)
break;
int addd = 0;
pair<int, int> mnm = {0, 0};
for (int i = 0; i < ctmp; i++)
{
if (mp[tmp[i].first][tmp[i].second].first == 1)
ans += mp[tmp[i].first][tmp[i].second].second,
mp[tmp[i].first][tmp[i].second].first = 0, addd = 1;
else if (mp[tmp[i].first][tmp[i].second].first == 2 &&
(mnm == make_pair(0, 0) ||
mp[tmp[i].first][tmp[i].second].first < mp[mnm.first][mnm.second].first))
{
mnm = {tmp[i].first, tmp[i].second};
}
}
if (!addd)
{
ans *= mp[mnm.first][mnm.second].second;
mp[mnm.first][mnm.second].first = 0;
}
}
cout << ans;
return 0;
}
E 防疫物资
树的直径
思路
题目描述便确定了题中所给是一棵树；
我们可以发现在每一个送货回路内，任意两节点都可以认为被走了一次（走过的道路可以组成路径），如果将这两个节点用道路连接，那么这两点原路径上的道路都可以被少走一次；
依此，我们找出这棵树上距离最远的两点即可，就是树的直径；
答案可以表示为原路径长-直径长+1；
树的直径可以由 双dfs法 或者 dp法 求得，时间复杂度相同，这里使用的是前者；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>rod[100005];
ll d[100005];
int pos;
int ds=-1;
void dfs(int u, int f,int lth)
{
ds++;
d[u]=d[f]+lth;
if(d[u]>d[pos])pos=u;
for (int i = 0; i < rod[u].size(); i++)
{
if (rod[u][i] == f)
continue;
dfs(rod[u][i], u,1);
ds++;
}
}
ll tree_r(int n)
{
for(int i=1;i<=n;i++)d[i]=0;
pos=0;
dfs(1,1,0);
int lth=ds;
// cout<<lth;
for(int i=1;i<=n;i++)d[i]=0;
dfs(pos,pos,0);
return lth-d[pos]+1;
}
int main()
{
int n,u,v;
cin>>n;
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&u,&v);
rod[u].push_back(v);
rod[v].push_back(u);
}
cout<<tree_r(n);
return 0;
}
F 有挂
线段树 / 树状数组
思路
区间和线段树模板题；
也许也可以用差分+树状数组解决；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5;
struct
{
int l, r;//l,r为节点的左右界
ll sum, lt;//sum为节点值，lt为懒标记
} segt[N << 2 | 1];
void pushdown(int p)//对懒标记进行下传
{
if (segt[p].lt)
{
segt[p << 1].sum += segt[p].lt * (segt[p << 1].r - segt[p << 1].l + 1);
segt[p << 1 | 1].sum += segt[p].lt * (segt[p << 1 | 1].r - segt[p << 1 | 1].l + 1);
segt[p << 1].lt += segt[p].lt;
segt[p << 1 | 1].lt += segt[p].lt;
segt[p].lt = 0;
}
}
void icg(int p, int cl, int cr, ll d)
{
if (cl <= segt[p].l && segt[p].r <= cr)
{
segt[p].sum += d * (segt[p].r - segt[p].l + 1);
segt[p].lt += d;
return;
}
pushdown(p);
int mid = segt[p].r + segt[p].l >> 1;
if (cl <= mid)
icg(p << 1, cl, cr, d);
if (cr >= mid + 1)
icg(p << 1 | 1, cl, cr, d);
segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
}
ll ick(int p, int cl, int cr)
{
if (cl <= segt[p].l && segt[p].r <= cr)
return segt[p].sum;
pushdown(p);
int mid = segt[p].r + segt[p].l >> 1;
ll val = 0;
if (cl <= mid)
val += ick(p << 1, cl, cr);
if (cr >= mid + 1)
val += ick(p << 1 | 1, cl, cr);
return val;
}
void build(int p, int cl, int cr)
{
segt[p].l = cl, segt[p].r = cr, segt[p].lt = 0, segt[p].sum = 0;
if (cl == cr)
{
segt[p].sum=0;
return;
}
int mid = cl + cr >> 1;
build(p << 1, cl, mid);
build(p << 1 | 1, mid + 1, cr);
segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
}
int main()
{
int n,m,x,op,l,r,k;
cin>>n>>m>>x;
build(1,1,n);
while(m--)
{
scanf("%d%d%d",&op,&l,&r);
if(op==1)
{
scanf("%d",&k);
icg(1,l,r,k/x+(!(k%x==0)));
}
else
{
printf("%lld\n",ick(1,l,r));
}
}
return 0;
}
G
数位dp，感谢汪佬（wxy）；
思路
构造状态表示 f [ i ] [ j ] f[i][j] f[i][j] 为以 i 结尾长度 m 的区间，如果按照 j 的二进制表示（从低到高第k位（第0位开始表示）为1代表第i-k日打球，0代表该日不打球），欢乐度合法的最大值（若 j 的表示非法，则该值即为 0 ）；
则有转移方程（状态合法时）
f
[
i
]
[
(
j
<
<
1
)
的
末
m
位
]
=
f
[
i
?
1
]
[
j
]
f
[
i
]
[
(
j
<
<
1
)
+
1
的
末
m
位
]
=
f
[
i
?
1
]
[
j
]
+
a
[
i
]
f[i][(j<<1)的末m位]=f[i-1][j]\\ f[i][(j<<1)+1的末m位]=f[i-1][j]+a[i]
f[i][(j<<1)的末m位]=f[i?1][j]f[i][(j<<1)+1的末m位]=f[i?1][j]+a[i]
其中取末m位的过程通过位运算完成；
由于m最大为8，二进制枚举每个状态不会造成很大的复杂度压力；
__builtin_popcount(t)是封装好的 bitcount 函数；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int f[N][1 << 9], n, m, a[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
for (int s = 0; s < (1 << m); ++s)
{
int t = (s << 1) & ((1 << m) - 1);
if (__builtin_popcount(t) <= m / 2)
f[i][t] = max(f[i][t], f[i - 1][s]);
if (__builtin_popcount(t) + 1 <= m / 2)
f[i][t | 1] = max(f[i][t | 1], f[i - 1][s] + a[i]);
}
int ans = 0;
for (int s = 0; s < (1 << m); ++s)
ans = max(ans, f[n][s]);
cout << ans;
}
H 爱美之心人皆有之
st表，二分
参考并简化了这份代码；
思路
st表是一种 O ( n log ? n ) O(n\log n) O(nlogn) 时空复杂度预处理， O ( 1 ) O(1) O(1) 时间复杂度求区间最大 / 小值的数据结构；
对于以 i 为左端点的所有区间而言，随着右端点的右移，区间极差会单调递增，我们可以依此二分；
找到区间极差等于 k 的最左右端点和最右右端点，便可以求出区间个数；
需要注意无解的情况；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int mi[N][21], ma[N][21], lg[N], a[N];
int ck_mi(int l, int r)
{
int k = lg[r - l + 1];
return min(mi[l][k], mi[r - (1 << k) + 1][k]);
}
int ck_ma(int l, int r)
{
int k = lg[r - l + 1];
return max(ma[l][k], ma[r - (1 << k) + 1][k]);
}
int main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
{
ma[i][0] = mi[i][0] = a[i], lg[i] = log2(i);
}
for (int i = 1; i <= 20; i++)
{
for (int j = 1; j + (1 << i) - 1 <= n; j++)
{
mi[j][i] = min(mi[j][i - 1], mi[j + (1 << (i - 1))][i - 1]);
ma[j][i] = max(ma[j][i - 1], ma[j + (1 << (i - 1))][i - 1]);
}
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
int l1 = i, r1 = n;
while (l1 < r1)
{
int mid = (l1 + r1) >> 1;
if (ck_ma(i, mid) - ck_mi(i, mid) >= k)
r1 = mid;
else
l1 = mid + 1;
}
int l2 = i, r2 = n;
while (l2 < r2)
{
int mid = (l2 + r2 + 1) >> 1;
if (ck_ma(i, mid) - ck_mi(i, mid) <= k)
l2 = mid;
else
r2 = mid - 1;
}
if(ck_ma(i, l1) - ck_mi(i, l1) == k)
ans += l2 - l1 + 1;
// printf("%d %d %d\n",i,l1,l2);
}
cout << ans;
return 0;
}
I 签签签到
愚人节快乐
思路
脑子空空，注意转义，也可以用raw字符串（ C++11功能）；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
cout<<"%d%\\n\"";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
cout<<R"(%d%\n")";
return 0;
}
