厦门市机场建设招投标网站,网络营销推广的力度,win2003搭建wordpress,内部网站建设、比赛链接
这场偏简单#xff0c;C是暴力#xff0c;D是变种背包#xff0c;E是map链表#xff0c;F是四维dp。DF出的很好#xff0c;建议做。 A Spoiler
题意#xff1a;
给你一个由小写英文字母和 | 组成的字符串 S S S。 S S S 中保证包含两个 |。
请删除两个|之间…比赛链接
这场偏简单C是暴力D是变种背包E是map链表F是四维dp。DF出的很好建议做。 A Spoiler
题意
给你一个由小写英文字母和 | 组成的字符串 S S S。 S S S 中保证包含两个 |。
请删除两个|之间的字符包括|本身并打印得到的字符串。
思路
用 string 的 find_first_of() 和 find_last_of() 成员函数可以很容易找到 | 的位置然后再用 substr() 成员函数提取字串即可。
code
#include iostream
#include cstdio
#include cstring
using namespace std;string str;int main(){cinstr;int astr.find_first_of(|),bstr.find_last_of(|);coutstr.substr(0,a)str.substr(b1);return 0;
}B Delimiter
题意
给你 N N N 个整数 A 1 , A 2 , … , A N A_1,A_2,\dots,A_N A1,A2,…,AN每行一个共 N N N 行。但是输入中没有给出 N N N。 此外下面的内容是有保证的 A i ≠ 0 A_i \neq 0 Ai0 ( 1 ≤ i ≤ N − 1 1 \le i \le N-1 1≤i≤N−1 ) A N 0 A_N 0 AN0
按此顺序打印 A N , A N − 1 , … , A 1 A_N, A_{N-1},\dots,A_1 AN,AN−1,…,A1。
思路
因为要逆序输出用个栈存一下读到 0 0 0 就停止读入然后输出。
code
#include iostream
#include cstdio
#include stack
using namespace std;int t;
stackint s;int main(){do{cint;s.push(t);}while(t);while(!s.empty()){couts.top()endl;s.pop();}return 0;
}C ABC
题意
给你三个序列 A ( A 1 , … , A N ) A(A_1,\ldots,A_N) A(A1,…,AN)、 B ( B 1 , … , B M ) B(B_1,\ldots,B_M) B(B1,…,BM) 和 C ( C 1 , … , C L ) C(C_1,\ldots,C_L) C(C1,…,CL)。
此外还给出了一个序列 X ( X 1 , … , X Q ) X(X_1,\ldots,X_Q) X(X1,…,XQ)。针对每个 i 1 , … , Q i1,\ldots,Q i1,…,Q 求解下面的问题
问题能否从 A A A、 B B B 和 C C C 中各选择一个元素使它们的和为 X i X_i Xi
思路
发现数据范围很小 N , M , L N,M,L N,M,L 最多就 100 100 100因此直接暴力即可。枚举三个数组中的每个元素算出所有可能的结果最后把得到的所有数放进set里之后查询即可
code
#include iostream
#include cstdio
#include set
using namespace std;
const int maxn105;int a[5][maxn],Q;int main(){for(int i1;i3;i){cina[i][0];for(int j1;ja[i][0];j)cina[i][j];}setint s;for(int i1;ia[1][0];i)for(int j1;ja[2][0];j)for(int k1;ka[3][0];k)s.insert(a[1][i]a[2][j]a[3][k]);for(cinQ;Q;Q--){int t;cint;puts((s.find(t)s.end())?No:Yes);}return 0;
} D String Bags
题意
最初有一个空字符串 S S S。 此外还有袋子 1 , 2 , … , N 1, 2, \dots, N 1,2,…,N每个袋子都包含一些字符串。 袋 i i i 包含 A i A_i Ai 个字符串 S i , 1 , S i , 2 , … , S i , A i S_{i,1}, S_{i,2}, \dots, S_{i,A_i} Si,1,Si,2,…,Si,Ai。
对 i 1 , 2 , … , N i 1, 2, \dots, N i1,2,…,N 重复以下步骤
选择并执行以下两个操作之一 支付 1 1 1 日元从袋子 i i i 中选择一个字符串并将其连接到 S S S 的末尾。不做任何操作。
给定字符串 T T T求使最后的 S S S 等于 T T T 所需的最小金额。 如果无法使最后的 S S S 等于 T T T则打印 -1。
限制因素 T T T 是由小写英文字母组成的字符串长度在 1 1 1 和 100 100 100 之间含。 N N N 是介于 1 1 1 和 100 100 100 之间的整数包含在内。 A i A_i Ai是介于 1 1 1和 10 10 10之间的整数包括 1 1 1和 10 10 10。 S i , j S_{i,j} Si,j是由小写英文字母组成的字符串长度在 1 1 1和 10 10 10之间包括 1 1 1和 10 10 10。
思路
看清楚题注意是按顺序从第 i i i 个袋子中取一个不能回头取也不能一个袋子取多个。所有 A C × 57 / W A × 1 AC\times57/WA\times1 AC×57/WA×1 的大概率是一个袋子取了多个字符串也就是说不能滚动数组优化。
读懂题之后这个题其实就是比较明显的背包了。设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示从前 i i i 个袋子中拼到 j j j 长度的最少花费如果不从第 i i i 个袋子选字符串那么就可以转移到 d p [ i 1 ] [ j ] dp[i1][j] dp[i1][j]如果从第 i i i 个袋子中选取一个字符串如果这个字符串长度为 l e n len len 并且这个字符串与 T T T 串的 j ∼ j l e n − 1 j\sim jlen-1 j∼jlen−1 部分子串正好相同这个字符串就可以拼到这里状态转移到 d p [ i 1 ] [ j l e n ] dp[i1][jlen] dp[i1][jlen]。
由于第 i i i 个袋子只能选一个字符串所以不能滚动数组优化乖乖二维DP。
code
#include iostream
#include cstdio
#include cstring
#include vector
using namespace std;
const int maxn105;
const int inf1e9;int n,m;
string t;
vectorvectorint dp(maxn,vectorint(maxn,inf));int main(){cint;nt.length();t t;cinm;for(int i0;im;i)dp[i][0]0;for(int i1,_;im;i){for(cin_;_;_--){string s;int len;cins;lens.length();for(int j1;jn;j){dp[i][j]min(dp[i][j],dp[i-1][j]);if(j-len0 t.substr(j-len1,len)s)dp[i][j]min(dp[i][j],dp[i-1][j-len]1);}}}if(dp[m][n]inf)cout-1endl;else coutdp[m][n]endl;return 0;
}E - Insert or Erase
题意
给你一个长度为 N N N 的序列 A ( A 1 , … , A N ) A(A_1,\ldots,A_N) A(A1,…,AN)。 A A A 中的元素是不同的。
请按照给出的顺序处理 Q Q Q 个查询。每个查询属于以下两种类型之一
1 x y在 A A A 中元素 x x x 后面紧接着插入 y y y。当给出此查询时保证 x x x 存在于 A A A 中。2 x从 A A A 中删除元素 x x x。当给出此查询时保证 x x x存在于 A A A中。
保证在处理完每一个查询后 A A A都不是空的并且其元素都是不同的。
处理完所有查询后打印 A A A。
思路
对操作 1 1 1需要查找 x x x 的位置然后在它后面插入 y y y对操作 2 2 2需要查找 x x x 的位置然后删掉它。因为题目非常贴心地告诉我们每个元素值都不一样所以可以用 m a p map map 建立起值到位置的映射而插入删除就需要使用链表了。
code
这里写的 头节点为 0 0 0 的循环双向链表。
#include iostream
#include cstdio
#include map
using namespace std;
const int maxn2e55;int n,Q;
int nxt[maxn1],pre[maxn1],a[maxn1],cnt;
mapint,int mp;int main(){cinn;for(int i1;in;i){cina[i];mp[a[i]]i;nxt[i-1]i;pre[i]i-1;}cntn;for(cinQ;Q;Q--){int op,x,y,p;cinop;if(op1){cinxy;pmp[x];a[cnt]y;mp[y]cnt;pre[cnt]p;nxt[cnt]nxt[p];pre[nxt[p]]cnt;nxt[p]cnt;}else {cinx;pmp[x];mp.erase(x);nxt[pre[p]]nxt[p];pre[nxt[p]]pre[p];}}for(int pnxt[0];p;pnxt[p]){couta[p] ;}return 0;
}F - Earn to Advance
题意
有一个网格网格中有 N N N 行和 N N N 列。让 ( i , j ) (i,j) (i,j) 表示从上面起第 i i i 行和从左边起第 j j j 列的正方形。
高桥最初在 ( 1 , 1 ) (1,1) (1,1) 个方格中的钱为零。
当高桥在 ( i , j ) (i,j) (i,j) 号方格时他可以在一次行动中完成以下其中一项
停留在同一位置并增加 P i , j P_{i,j} Pi,j个数字。从他的钱中支付 R i , j R_{i,j} Ri,j 并移动到 ( i , j 1 ) (i,j1) (i,j1) 格。从他的钱中支付 D i , j D_{i,j} Di,j 并移动到 ( i 1 , j ) (i1,j) (i1,j) 格。
他不能走会使他的金钱变为负数或使他离开棋盘的一步棋。
如果高桥采取最优行动他需要下多少步棋才能到达 ( N , N ) (N,N) (N,N) 位置
思路
当看到 N ≤ 80 N\le80 N≤80 的时候就不对劲起来了。可以跑 N 4 N^4 N4甚至还能带点常数。
我们到达某个位置的时候最少需要描述横坐标纵坐标时间剩余金钱 四个状态参数。而金钱这东西我们可以先在一个地方打很长时间的工赚很多钱再向后走这样可能是更优的。而我们在打工的时候很难知道赚多少合适也不知道后面有没有更好的打工地点。那么如何解决呢
考虑到我们走过一个路径到达 ( i , j ) (i,j) (i,j) 点的时候路径上经过的所有点我们都可以提前在那打工显然我们在最赚钱的地方打工。对这个打工地点我们如果在 ( i , j ) (i,j) (i,j) 上需要钱那么之前离开这个打工地点之前可以先不走留下来多赚几天钱。也就是说我们相当于可以随时随地回到前面路径上的任何一个点来赚钱。
但是我们并不知道我们是如何到达 ( i , j ) (i,j) (i,j) 的自然也不知道路径上有什么点。但是我们只关心经过的最赚钱的那个地点也就是我们返回前面打工的地点加上这题可以跑 N 4 N^4 N4 那么我们就可以把这个点放进 d p dp dp 里具体来说设 d p [ i ] [ j ] [ x ] [ y ] dp[i][j][x][y] dp[i][j][x][y] 表示到达 ( i , j ) (i,j) (i,j) 并在 ( x , y ) (x,y) (x,y) 打工的最少花费时间和最多剩余金钱。
这里 d p dp dp 是个 p a i r pair pair 类型存储最少花费时间和最多剩余金钱。那么哪种值算最优答案是花费时间最少的最优其次剩余金钱最多的最优。因为我们可以随时回去赚钱所以我们不挣闲钱只要钱够就绝对不多花一天时间挣钱。因为我们推最优状态的最优推理时经过的路径上的点一定是越来越挣钱的你转移过来的时候剩余的最多的金钱最多不会超过前面路径上的 最赚钱地点上 一天赚的钱也就小于在 ( x , y ) (x,y) (x,y) 上一天赚的钱花费时间少的多花一天时间在 ( x , y ) (x,y) (x,y) 挣钱手上的钱一定更多。因此这样排序是正确的。 d p [ i ] [ j ] [ x ] [ y ] dp[i][j][x][y] dp[i][j][x][y] 可以由 d p [ i − 1 ] [ j ] [ x ] [ y ] dp[i-1][j][x][y] dp[i−1][j][x][y] 和 d p [ i ] [ j − 1 ] [ x ] [ y ] dp[i][j-1][x][y] dp[i][j−1][x][y] 转移得到而转移过来时分别需要花费 D [ i − 1 ] [ j ] D[i-1][j] D[i−1][j] 和 R [ i ] [ j − 1 ] R[i][j-1] R[i][j−1] 的代价这时候就可能需要去 ( x , y ) (x,y) (x,y) 赚钱。
假设从 d p [ i − 1 ] [ j ] [ x ] [ y ] dp[i-1][j][x][y] dp[i−1][j][x][y] 转移过来设在 ( i , j ) (i,j) (i,j) 这里花费了 t m tm tm 时间挣钱手上剩余 l s t lst lst 钱挣钱效率 c P [ x ] [ y ] cP[x][y] cP[x][y]转移代价 w D [ i − 1 ] [ j ] wD[i-1][j] wD[i−1][j]需要花费 k k k 天来赚钱就有 l s t k ∗ c − w ≥ 0 lstk*c-w\ge 0 lstk∗c−w≥0 k ≥ w − l s t c k\ge \frac{w-lst}{c} k≥cw−lst k ⌈ w − l s t c ⌉ k\left\lceil\frac{w-lst}{c}\right\rceil k⌈cw−lst⌉
另外我们在 ( i , j ) (i,j) (i,j) 的时候可以把之后挣钱的地点改为 ( i , j ) (i,j) (i,j)这时 d p [ i ] [ j ] [ i ] [ j ] dp[i][j][i][j] dp[i][j][i][j] 可以由所有 d p [ i ] [ j ] [ x ] [ y ] ( 1 ≤ x ≤ i , 1 ≤ y ≤ j ) dp[i][j][x][y]\quad(1\le x\le i,1\le y\le j) dp[i][j][x][y](1≤x≤i,1≤y≤j) 推过来。
code
#include iostream
#include cstdio
#include queue
#define mk make_pair
using namespace std;
typedef long long ll;
const int maxn85;
const ll inf1e18;int n;
vectorvectorll P(maxn,vectorll(maxn));
vectorvectorll R(maxn,vectorll(maxn));
vectorvectorll D(maxn,vectorll(maxn));vectorvectorvectorvectorpairll,ll dp(maxn,vectorvectorvectorpairll,ll (maxn,vectorvectorpairll,ll (maxn,vectorpairll,ll (maxn,mk(inf,0)))));pairll,ll g(pairll,ll x,pairll,ll y){if(x.first!y.first)return (x.firsty.first)?x:y;return (x.secondy.second)?x:y;
}int main(){cinn;for(int i1;in;i)for(int j1;jn;j)cinP[i][j];for(int i1;in;i)for(int j1;jn;j)cinR[i][j];for(int i1;in;i)for(int j1;jn;j)cinD[i][j];dp[1][1][1][1]mk(0,0);for(int i1;in;i){for(int j1;jn;j){for(int x1;xi;x){for(int y1;yj;y){ll k,c,tm,lst,w;if(i1 i-1x){tmdp[i-1][j][x][y].first;//花了多少时间 lstdp[i-1][j][x][y].second;//剩了多少钱 wD[i-1][j];//走过来需要花的钱 cP[x][y];//挣钱的效率 kmax(0ll,(w-lstc-1)/c);//需要花多长时间挣钱 dp[i][j][x][y]g(dp[i][j][x][y],mk(tmk1,lstk*c-w));}if(j1 j-1y){tmdp[i][j-1][x][y].first;lstdp[i][j-1][x][y].second;wR[i][j-1];cP[x][y];kmax(0ll,(w-lstc-1)/c);dp[i][j][x][y]g(dp[i][j][x][y],mk(tmk1,lstk*c-w));}dp[i][j][i][j]g(dp[i][j][i][j],dp[i][j][x][y]);}}}}coutdp[n][n][n][n].firstendl;return 0;
}
