- A. Girls Band Party
- B. So Easy
- C. Image Processing
- D. Easy Problem
- E. XOR Tree
- F. Function!
- G. Pot!!
- H. Delivery Route
- I. Base62
- J. Toad’s Travel
- K. Largest Common Submatrix
- L. Xian Xiang
- M. Crazy Cake
- N. Fibonacci Sequence
A. Girls Band Party
大意：
给出n张牌，每张牌都有花色和名字，以及价值，只能选择不同名字的五张牌，有5种奖励名字和一种奖励花色，和奖励名字相同的名字可以提供10%的加成，相同的颜色可以提供20%的加成，这些加成可以累加到最后一起结算，问最大的价值和是多少
思路：
分组背包问题，但是需要加一个维度记录加成的等级，这样最后再计算价值和即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
int t, n,level[N],dp[N][10][20];
struct node{
string name;
string color;
int val;
} a[N];
unordered_map<string, int> mp;
vector<int> g[N];
int main(){
cin>>t;
for(int j = 0;j < 6; ++j)
for(int i = 0;i < 16; ++i)
dp[0][j][i] = -0x3f3f3f3f;
while(t--){
cin>>n;
mp.clear();
int idx = 1;
for (int i = 1; i <= n;i++){
cin >> a[i].name >> a[i].color >> a[i].val;
level[i] = 0;
if(mp[a[i].name]==0){
g[idx].clear();
mp[a[i].name] = idx++;
}
g[mp[a[i].name]].push_back(i);
}
for (int i = 1; i <= 5;i++){
string name;
cin >> name;
for (int j = 1; j <= n;j++){
if(a[j].name==name){
level[j] += 1;
}
}
}
string color;
cin >> color;
for (int i = 1; i <= n;i++){
if(color==a[i].color){
level[i] += 2;
}
}
dp[0][0][0] = 0;
for (int i = 1; i < idx;i++){
for (int j = 1; j <= 5;j++){
for (int k = 0; k <= 15;k++){
dp[i][j][k] = dp[i - 1][j][k];
}
}
for (int p = 0; p < g[i].size(); p++){
for (int j = 1; j <= 5; j++){
for (int k = level[g[i][p]]; k <= 15; k++){
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - level[g[i][p]]] + a[g[i][p]].val);
}
}
}
}
int res = 0;
for (int i = 0; i <= 15;i++){
res = max(res, dp[idx-1][5][i] + dp[idx-1][5][i] * i / 10);
}
cout << res << endl;
}
return 0;
}
B. So Easy
大意：
初始是一个全为0的数组，每次操作都是将一列或者一行全加1，最后选择一个数将其置为-1，现在给出最后的结果，问-1的位置在置为-1前是多少
思路：
因为数据量很小，直接暴力每一行和每一列，都减去该列（行）最小的数字，最后看-1的位置是多少
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n,mp[N][N],x,y;
int main(){
cin >> n;
for (int i = 0; i < n;i++){
for (int j = 0; j < n;j++){
cin >> mp[i][j];
if(mp[i][j]==-1){
x = i;
y = j;
}
}
}
for (int i = 0; i < n;i++){
int minn = 0x3f3f3f3f;
for (int j = 0; j < n;j++){
if(minn>mp[i][j]&&(!(i==x&&j==y))){
minn = mp[i][j];
}
}
for (int j = 0; j < n;j++){
mp[i][j] -= minn;
}
}
for (int j = 0; j < n;j++){
int minn = 0x3f3f3f3f;
for (int i = 0; i < n;i++){
if(minn>mp[i][j]&&(!(i==x&&j==y))){
minn = mp[i][j];
}
}
for (int i = 0; i < n;i++){
mp[i][j] -= minn;
}
}
cout << -(mp[x][y] + 1) << endl;
return 0;
}
C. Image Processing
咕咕咕
D. Easy Problem
咕咕咕
E. XOR Tree
咕咕咕
F. Function!
大意：
（图源：https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/106162905）
思路：
当\(a<=\sqrt{n}\)时直接跳着做，否则直接O(1)的复杂度求出解
需要注意的是，因为n很大，当他去乘别的数的时候要先取模再乘，不能乘完再取模，否则就wa了....
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
LL n, res, inv2, inv6;
const LL mod = 998244353;
LL qmi(LL a, LL k, LL p)
{
LL res = 1 % p; // res记录答案, 模上p是为了防止k为0，p为1的特殊情况
while (k)
{ // 只要还有剩下位数
if (k & 1)
res = (LL)res * a % p; // 判断最后一位是否为1，如果为1就乘上a，模上p, 乘法时可能爆int，所以变成long long
k >>= 1; // 右移一位
a = (LL)a * a % p; // 当前a等于上一次的a平方，取模，平方时可能爆int，所以变成long long
}
return res;
}
LL s1(LL k)
{
k = k % mod;
return k * (k + 1) % mod * inv2 % mod;
}
LL s2(LL k)
{ //平方和
return k %= mod, k * (k + 1) % mod * (k * 2 + 1) % mod * inv6 % mod;
}
int main()
{
cin >> n;
inv2 = qmi(2, mod - 2, mod), inv6 = qmi(6, mod - 2, mod);
LL a;
for (a = 2; a * a <= n; a++)
{
LL sum = a - 1;
LL pre = a, now = a * a;
LL t=1;
for (LL i = 2; i <= n; i++)
{
if (sum + now - pre > n)
{
res = (res + a * (n - sum) % mod * (i - 1) % mod) % mod;
break;
}
res = (res + a * (i - 1) % mod * (now - pre) % mod) % mod;
sum += now - pre;
pre = now;
now = now * a;
}
}
res = (res + ((n + 1) % mod * (s1(n) - s1(a - 1) + mod) % mod) - (s2(n) - s2(a - 1) + mod) % mod + mod) % mod;
cout << res << endl;
return 0;
}
G. Pot!!
大意：
一个数组初始均为1，有两个操作，一个是修改：将区间\([l,r]\)的值乘上\(x,(1<=x<=10)\)
另一个是查询：查询区间\([l,r]\)上的数，能被2，3，5，7整除次数的最大值。
思路：
直接线段树维护被2 3 5 7 整除的次数最大值以及全部的最大值即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
struct node{
int sum2, sum3, sum5, sum7, maxn,lazy2,lazy3,lazy5,lazy7;
}dat[N << 2];
int a[N], n, m,prime[4]={2,3,5,7};
// 上传标记，每次左右子树建树/区间修改完都需要上传
void pushup(int rt) {
dat[rt].sum2 = max(dat[rt << 1].sum2, dat[rt << 1 | 1].sum2);
dat[rt].sum3 = max(dat[rt << 1].sum3, dat[rt << 1 | 1].sum3);
dat[rt].sum5 = max(dat[rt << 1].sum5, dat[rt << 1 | 1].sum5);
dat[rt].sum7 = max(dat[rt << 1].sum7, dat[rt << 1 | 1].sum7);
dat[rt].maxn = max(max(dat[rt].sum2, dat[rt].sum3), max(dat[rt].sum5, dat[rt].sum7));
}
// 建树
void build(int rt, int l, int r) {
if (l == r) { // 递归到叶节点
dat[rt].sum2 = dat[rt].sum3 = dat[rt].sum5 = dat[rt].sum7 = 0;
dat[rt].lazy2 = dat[rt].lazy3 = dat[rt].lazy5 = dat[rt].lazy7 = 0;
dat[rt].maxn = 0;
return;
}
// 递归建立左右子树
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt); // 上传
}
// 下传，下传标记，同时改变dat数组
void pushdown(int rt, int l, int r) {
if (dat[rt].lazy2) {
dat[rt << 1].lazy2 += dat[rt].lazy2;
dat[rt << 1 | 1].lazy2 += dat[rt].lazy2;
dat[rt << 1].sum2 += dat[rt].lazy2;
dat[rt << 1 | 1].sum2 += dat[rt].lazy2;
dat[rt].lazy2 = 0;
}
if (dat[rt].lazy3) {
dat[rt << 1].lazy3 += dat[rt].lazy3;
dat[rt << 1 | 1].lazy3 += dat[rt].lazy3;
dat[rt << 1].sum3 += dat[rt].lazy3;
dat[rt << 1 | 1].sum3 += dat[rt].lazy3;
dat[rt].lazy3 = 0;
}
if (dat[rt].lazy5) {
dat[rt << 1].lazy5 += dat[rt].lazy5;
dat[rt << 1 | 1].lazy5 += dat[rt].lazy5;
dat[rt << 1].sum5 += dat[rt].lazy5;
dat[rt << 1 | 1].sum5 += dat[rt].lazy5;
dat[rt].lazy5 = 0;
}
if (dat[rt].lazy7) {
dat[rt << 1].lazy7 += dat[rt].lazy7;
dat[rt << 1 | 1].lazy7 += dat[rt].lazy7;
dat[rt << 1].sum7 += dat[rt].lazy7;
dat[rt << 1 | 1].sum7 += dat[rt].lazy7;
dat[rt].lazy7 = 0;
}
dat[rt << 1].maxn = max(max(dat[rt << 1].sum2, dat[rt << 1].sum3), max(dat[rt << 1].sum5, dat[rt << 1].sum7));
dat[rt << 1 | 1].maxn = max(max(dat[rt << 1 | 1].sum2, dat[rt << 1 | 1].sum3), max(dat[rt << 1 | 1].sum5, dat[rt << 1 | 1].sum7));
return;
}
// 区间修改: [L, R] += x
void modify(int rt, int l, int r, int L, int R, int x2,int x3,int x5,int x7) {
if (L <= l && r <= R) { // 如果当前区间被完全包含
dat[rt].sum2 += x2;
dat[rt].lazy2 += x2;
dat[rt].sum3 += x3;
dat[rt].lazy3 += x3;
dat[rt].sum5 += x5;
dat[rt].lazy5 += x5;
dat[rt].sum7 += x7;
dat[rt].lazy7 += x7;
return ;
}
pushdown(rt, l, r); // 下传
// 递归左右子树修改区间
int mid = (l + r) >> 1;
if (L <= mid)
modify(rt << 1, l, mid, L, R, x2, x3, x5, x7);
if (mid < R) modify(rt << 1 | 1, mid + 1, r, L, R, x2, x3, x5, x7);
pushup(rt); // 上传
return;
}
// 区间查询:获得[L, R]的区间和
LL query(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) return dat[rt].maxn; // 如果[l, r]被完全包含于[L, R]
pushdown(rt, l, r); // 标记下传
// 递归加上左右子树
int mid = (l + r) >> 1;
LL res = 0;
if (L <= mid) res = max(res,query(rt << 1, l, mid, L, R));
if (mid < R) res = max(res,query(rt << 1 | 1, mid + 1, r, L, R));
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) a[i]=1; // 读入数组
build(1, 1, n); // 建树
char op[10];
for (int i = 1, a, b, x; i <= m; ++i) {
scanf("%s", &op);
if (strcmp(op,"MULTIPLY")==0) {
scanf("%d%d%d", &a, &b, &x);
int xn[4] = {0, 0, 0, 0};
for (int j = 0; j < 4;j++){
while(x%prime[j]==0){
xn[j]++;
x /= prime[j];
}
}
modify(1, 1, n, a, b, xn[0], xn[1], xn[2], xn[3]); // 区间修改
}
else {
scanf("%d%d", &a, &b);
printf("ANSWER %lld\n", query(1, 1, n, a, b)); // 区间查询
}
}
return 0;
}
H. Delivery Route
大意：
在一张既有有向边又有无向边的图上求出每个点到源点的最短距离，保证有向边不会形成有向环
思路：
先把无向边建的图分成很多连通块，缩成超级点。再加上有向边后，整张图就变成一张dag。然后拓扑排序求最短路，当处理超级点时，用堆优化版dijkstra处理
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int const N = 3e4 + 10, M = 2e5 + 10;
int e[M], ne[M], w[M], idx, h[M];
int t, r, p, source;
int id[N];
vector<int> block[N];
int bcnt;
int st[N];
int dis[N];
queue<int> q;
int din[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
// 按照连通块缩点
void dfs(int u, int cnt) {
id[u] = cnt;
block[cnt].push_back(u);
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!id[j]) dfs(j, cnt);
}
}
// 堆优化版dijkstra算法求连通块内的最短路
void dijkstra(int bid) {
priority_queue<PII, vector<PII>, greater<PII> >heap;
for (auto b: block[bid]) heap.push({dis[b], b});
while (heap.size()) {
auto t = heap.top();
heap.pop();
int distance = t.first, ver = t.second;
if (st[ver]) continue;
st[ver] = 1;
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > distance + w[i]) {
dis[j] = distance + w[i];
if (id[ver] == id[j]) heap.push({dis[j], j}); // 如果是一个超级点内才能更新
}
if (id[ver] != id[j]) { // 不在一个超级点内，那么需要按照拓扑排序逻辑更新
din[id[j]]--;
if (!din[id[j]]) q.push(id[j]);
}
}
}
}
// 拓扑排序求最短路
void top_sort() {
for (int i = 1; i <= bcnt; ++i)
if (!din[i]) q.push(i);
memset(dis, 0x3f, sizeof dis);
memset(st, 0, sizeof st);
dis[source] = 0;
while (q.size()) {
auto t = q.front();
q.pop();
dijkstra(t);
}
}
int main() {
memset(h, -1, sizeof h);
cin >> t >> r >> p >> source;
for (int i = 1; i <= r; ++i) { // 读入无向边
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
for (int i = 1; i <= t; ++i) { // 把所有点按照连通块划分为超级点
if (!id[i]) dfs(i, ++bcnt);
}
for (int i = 1; i <= p; ++i) { // 读入有向边
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
add(a, b, c);
din[id[b]]++;
}
top_sort(); // 拓扑排序求最短路
for (int i = 1; i <= t; ++i) { // 判断是否有最短路
if (dis[i] > 0x3f3f3f3f / 2) cout << "NO PATH\n";
else cout << dis[i] << endl;
}
return 0;
}
I. Base62
大意：
给出一个字符串，要求从n进制转化为m进制
思路：
短除法模板题
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
typedef long long LL;
int n,m;
char str1[N],str2[N];
int t[N],ans[N];
int getnum(char ch) //字符转数字
{
if(ch <= '9') return ch-'0';
else if(ch <= 'Z') return 10+ch-'A';
else return 36+ch-'a';
}
char getch(int num) //数字转字符
{
if(num <= 9) return num+'0';
else if(num <= 35) return num-10+'A';
else return num-36+'a';
}
void solve()
{
int len = strlen(str1);
for(int i = 0; i < len; i++) //先把字符串变成数组,高位->低位
t[i] = getnum(str1[i]);
int j = 0,k = 0;
while(j < len)
{
for(int i = j; i < len-1; i++) //除以m,把余数加到下一位
{
t[i+1] += t[i] % m * n;
t[i] /= m;
}
ans[k++] = t[len-1]%m; //个位数余m
t[len-1] /= m;
while(j < len && !t[j]) j++; //最高位是0,j++
}
for(int i = 0; i < k; i++) //逆序变成字符串
{
str2[i] = getch(ans[k-i-1]);
}
}
int main()
{
int t;
memset(ans, 0, sizeof(ans));
memset(str2, 0, sizeof(str2));
cin>>n>>m;
cin>>str1;
solve();
cout<<str2<<endl;
}
J. Toad’s Travel
咕咕咕
K. Largest Common Submatrix
大意：
给两个\(n*m\)的矩阵,矩阵的元素为1~\(n*m\)的全排列,求两个矩阵的最大相同子矩形的面积(元素数)
思路：
由于两个矩阵都是全排列，可以先标记出a矩阵中的元素在b矩阵中出现的位置，然后预处理一下a矩阵中元素向右能延伸多少，标记为l数组，然后就可以转化为经典的单调栈处理最大矩形的问题（只不过这个是旋转了90度的）,还需要注意的是，需要保证向下也是能延伸的，所以还需要标记一个l2数组
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e3+100;
int l[N][N],l2[N][N],a[N][N],b[N][N];
struct Node{
int h,w;
Node(int H,int W){
h=H;
w=W;
}
};
unordered_map<int, pair<int, int>> pos;//map超时
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
l[i][j] = 1;
l2[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&b[i][j]);
pos[b[i][j]] = {i, j};
}
}
for(int i=1;i<=n;i++){
for(int j=m-1;j>=1;j--)
{
int x1=i,y1=j;
int x2=pos[a[i][j]].first;
int y2=pos[a[i][j]].second;
if(a[x1][y1+1]==b[x2][y2+1])
l[x1][y1]=l[x1][y1+1]+1;
}
}
for(int i=n-1;i>=1;i--){
for(int j=1;j<=m;j++){
int x1=i,y1=j;
int x2=pos[a[i][j]].first;
int y2=pos[a[i][j]].second;
if(a[x1+1][y1]==b[x2+1][y2])
l2[x1][y1]=l2[x1+1][y1]+1;
}
}
int ans=0;
for(int i=1;i<=m;i++){
int mark=1;
while(mark<=n){
stack<Node>st;
for(int j=mark;j<=mark+l2[mark][i]-1;j++){
int w=0;
while(st.size()&&st.top().h>l[j][i]){
w+=st.top().w;
ans=max(ans,w*st.top().h);
st.pop();
}
st.push(Node(l[j][i],w+1));
}
int w=0;
while(st.size()){
w+=st.top().w;
ans=max(ans,w*st.top().h);
st.pop();
}
mark+=l2[mark][i];
}
}
cout<<ans<<endl;
return 0;
}
L. Xian Xiang
咕咕咕
M. Crazy Cake
咕咕咕
N. Fibonacci Sequence
签到，输出前五个斐波那契数
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int main(){
cout << "1 1 2 3 5" << endl;
return 0;
}