seo网站建设方案,建个企业网站需要多少钱,wordpress 搜索模版,网上投资项目的平台有哪些这里感谢一下计算机学术交流协会会长#xff0c;acm实验室的中坚成员#xff0c;以及本次比赛的出题人之一孙昱涵将他的账号借给了我。
回顾一下的话#xff0c;这场的难度其实不是很大#xff0c;不过对招新的新手来说难度还是挺大的。去掉签到都没签出来的选手的话… 这里感谢一下计算机学术交流协会会长acm实验室的中坚成员以及本次比赛的出题人之一孙昱涵将他的账号借给了我。
回顾一下的话这场的难度其实不是很大不过对招新的新手来说难度还是挺大的。去掉签到都没签出来的选手的话可以看到大部分选手都只能做出四五题左右最前面那两个是打星的非正式参赛选手。
题目难度我觉得按顺序应该是 A , I , L C , E , F D , J , K B G , H A,I,L\lt C,E,F\lt D,J,K\lt B\lt G,H A,I,LC,E,FD,J,KBG,H 。
虽然不连校园网大概率连不上不过姑且还是放一下比赛链接 A.区间次大值
题面 思路
可以跑 n 2 n^2 n2所以直接暴力枚举左端点 l l l然后向右移动右端点 r r r维护住区间的次大值边移动边统计答案即可。
话说赛时评测机炸了这题跑出来的全是WA。
code
#include iostream
#include cstdio
using namespace std;
const int maxn1e35;
typedef long long ll;int n,a[maxn];
ll ans0;int main(){cinn;for(int i1;in;i)cina[i];for(int l1;ln;l){int mxa[l],mx20;for(int rl1;rn;r){if(a[r]mx){mx2mx;mxa[r];}else if(a[r]mx2){mx2a[r];}ansmx2;}}coutans;return 0;
}B.上课签到
题面 思路
不考虑统计路径上最大 a i a_i ai 的条件的话就是个普通的最短路。体感上感觉直接去找小于等于 h h h 的所有路径上的最大 a i a_i ai 是不太可能的。但是如果我们验证答案就会很简单也就是我们提前设定一个最大的 a i a_i ai 值然后跑 d i j k s t r a dijkstra dijkstra这样一次验证就是 ( n m ) l o g n (nm)log\,n (nm)logn 的复杂度。
而这个答案具有单调性即如果答案是 x x x那么所有大于 x x x 的答案也是可以通过验证的。这样就可以二分答案了。总的时间复杂度就是 ( n m ) l o g 2 n (nm)log^2n (nm)log2n可以通过。
这个二分既可以是值域上的二分也可以是对点的 a i a_i ai 值排序然后在上面二分。
code
值域二分
#include iostream
#include cstdio
#include vector
#include queue
#define mk make_pair
using namespace std;
typedef long long ll;
const int maxn1e45;
const int maxm2e45;
const ll inf1e18;int n,m,st,ed;
ll H,a[maxn];int head[maxn],cnt;
struct edge{int nxt,v;ll w;
}e[maxm1];
void add(int u,int v,ll w){e[cnt].vv;e[cnt].ww;e[cnt].nxthead[u];head[u]cnt;
}bool dijkstra(ll bound){vectorll d(maxn,inf);vectorbool vis(maxn,false);priority_queuepairll,int,vectorpairll,int ,greaterpairll,int h;d[st]0;h.push(mk(0ll,st));while(!h.empty()){int uh.top().second;h.pop();if(ued)return true;if(vis[u])continue;else vis[u]true;for(int ihead[u],v,w;i;ie[i].nxt){ve[i].v;we[i].w;if(d[u]wH || a[v]bound)continue;if(d[v]d[u]w){d[v]d[u]w;h.push(mk(d[v],v));}}}return false;
}int main(){cinnmstedH;for(int i1;in;i)cina[i];for(int i1,u,v,w;im;i){cinuvw;add(u,v,w);add(v,u,w);}ll la[st],r1e18,mid;while(lr){mid(lr)1;if(dijkstra(mid))rmid;else lmid1;}cout((l1e18)?-1:l)endl;return 0;
} 点集二分
#include iostream
#include cstdio
#include vector
#include queue
#include algorithm
#define mk make_pair
using namespace std;
typedef long long ll;
const int maxn1e45;
const int maxm2e45;
const ll inf1e9;int n,m,st,ed;
ll H,a[maxn],tmp[maxn];int head[maxn],cnt;
struct edge{int nxt,v,w;
}e[maxm1];
void add(int u,int v,int w){e[cnt].vv;e[cnt].ww;e[cnt].nxthead[u];head[u]cnt;
}bool dijkstra(ll bound){if(bounda[st])return false;vectorll d(maxn,inf);vectorbool vis(maxn,false);priority_queuepairll,int,vectorpairll,int ,greaterpairll,int h;d[st]0;h.push(mk(0ll,st));while(!h.empty()){int uh.top().second;h.pop();if(ued)return true;if(vis[u])continue;else vis[u]true;for(int ihead[u],v,w;i;ie[i].nxt){ve[i].v;we[i].w;if(d[u]wH || a[v]bound)continue;if(d[u]wd[v]){d[v]d[u]w;h.push(mk(d[v],v));}}}return false;
}int main(){cinnmstedH;for(int i1;in;i)cina[i],tmp[i]a[i];for(int i1,u,v,w;im;i){cinuvw;add(u,v,w);add(v,u,w);}sort(tmp1,tmpn1);if(!dijkstra(tmp[n])){cout-1;return 0;}int l1,rn,mid;while(lr){mid(lr)1;if(dijkstra(tmp[mid]))rmid;else lmid1;}couttmp[l]endl;return 0;
} C.魔法森林一
题面 思路
跟着操作跑一遍就行了这题没人写是我没想到的都被吓住了。
这个题的难点在于传送法阵的强制传送机制。首先需要将两个法阵的位置对应起来其次需要在移动的时候实现这个传送。
对应法阵位置的方法因为一个一个字符读取图的时候一定会先遇到一个字母再遇到一个相同字母。所以存储第一个字母的位置在读到第二个字母的时候将两个坐标用map相互映射一下就好。
code
#include iostream
#include cstdio
#include cstring
#include map
using namespace std;
const int maxn5005;int n,m;
string mp[maxn];
mappairint,int,pairint,int sp;
mapchar,pairint,int tmp;int fx[]{1,-1,0,0},fy[]{0,0,1,-1};int main(){cinnm;for(int i1;in;i){cinmp[i];mp[i] mp[i];for(int j1;jm;j){if(mp[i][j]!. mp[i][j]!#){if(tmp.find(mp[i][j])tmp.end())tmp[mp[i][j]]make_pair(i,j);else {pairint,int atmp[mp[i][j]],bmake_pair(i,j);sp[a]b;sp[b]a;}}}}int x,y,q;cinxyq;for(;q;q--){char op;cinop;int st;switch(op){case D:st0;break;case U:st1;break;case R:st2;break;case L:st3;break;}int vxxfx[st],vyyfy[st];if(vx1 || vxn || vy1 || vym || mp[vx][vy]#)continue;if(mp[vx][vy]!.){xsp[make_pair(vx,vy)].first;ysp[make_pair(vx,vy)].second;}else {xvx;yvy;}}coutx yendl;return 0;
}D.魔法森林二
题面 思路
一个耿直的BFS赛时没有写出来的就nm离谱代码能力不行导致的。
注意一下传送阵是强制传送的。
对传送法阵的处理还是和 C C C 题一致难点主要是要想明白在BFS时需要使用 v i s vis vis 数组对已经经过的位置进行标记在碰到传送阵时这个标记是标记传送前的位置还是传送后的位置。
我们 v i s vis vis 数组的职责是标记已经经过的位置因为走这个位置之后所有可能的行走路径都会重复。换句话说我们如果走某个位置之后所有可能的行走路径都会重复那么就对这个位置进行标记。我们在进入一个位置的传送阵之后我们还可以从另一个传送阵再传回来这样有可能到终点更快而我们如果再走前一个传送阵后面就会重复所以我们应该标记的是传送前的法阵位置。
code
#include iostream
#include cstdio
#include cstring
#include map
#include queue
#define mk make_pair
using namespace std;
const int maxn5005;int n,m;
string mp[maxn];
mappairint,int,pairint,int sp;
mapchar,pairint,int tmp;
int vis[maxn][maxn];int fx[]{1,-1,0,0},fy[]{0,0,1,-1};int main(){cinnm;for(int i1;in;i){cinmp[i];mp[i] mp[i];for(int j1;jm;j){if(mp[i][j]!. mp[i][j]!#){if(tmp.find(mp[i][j])tmp.end())tmp[mp[i][j]]make_pair(i,j);else {pairint,int atmp[mp[i][j]],bmake_pair(i,j);sp[a]b;sp[b]a;}}}}int sx,sy,ex,ey;queuepairint,int q;cinsxsyexey;vis[sx][sy]1;q.push(mk(sx,sy));while(!q.empty()){int uxq.front().first,uyq.front().second;q.pop();if(uxex uyey){coutvis[ux][uy]-1;return 0;}for(int i0,x,y;i4;i){xuxfx[i];yuyfy[i];if(x1 || xn || y1 || ym || mp[x][y]# || vis[x][y])continue;if(mp[x][y].){vis[x][y]vis[ux][uy]1;q.push(mk(x,y));}else {int txsp[make_pair(x,y)].first,tysp[make_pair(x,y)].second;vis[tx][ty]vis[ux][uy]1;q.push(mk(tx,ty));}}}cout-1endl;return 0;
}E.LOP
题面 思路
CF原题这个题主要是诱导你往游戏规则上想实际上由于最后一局就是决胜局因此最后一个赢的就是赢家。
code
#include iostream
#include cstdio
#include cstring
using namespace std;string s;int main(){cins;couts[s.length()-1];return 0;
}F.跳格子
题面 思路
对某个位置的砖块它可以由前两个砖块转移过来因此走到第 i i i 个位置的砖块的方法数就是到达 i − 1 i-1 i−1 和 i − 2 i-2 i−2 位置上的方法数之和。直接递推即可。
code
#include iostream
#include cstdio
using namespace std;
typedef long long ll;
const ll mod1e97;
const int maxn1e65;int n;
ll dp[maxn];int main(){cinn;dp[1]dp[2]1;for(int i3;in;i){dp[i](dp[i-1]dp[i-2])%mod;}coutdp[n];return 0;
}G.猜数字
题面 思路
魔王题之一概率区间dp。
我们在随机取数的时候除了一发入魂的情况这个区间都是在一段一段变小的。而转移到某一段子区间的时候如果我们知道这个子区间的期望那么我们就可以算出原区间由这个情况转移过来的期望。而子区间也是这样来算每一种情况贡献的期望。
那么思路就比较明显了设 d p [ i ] [ j ] dp[i][j] dp[i][j] 为区间 [ i , j ] [i,j] [i,j] 生成 x x x 的期望。发现下次生成的数只有三种情况
正好生成 x x x这时期望贡献就是 1 j − i 1 \dfrac1{j-i1} j−i11。生成的数为 k ( i ≤ k x ) k\quad(i\le k\lt x) k(i≤kx) 时这时候期望为 1 j − i 1 ∗ ( d p [ k ] [ j ] 1 ) \dfrac1{j-i1}*(dp[k][j]1) j−i11∗(dp[k][j]1)生成的数为 k ( x k ≤ j ) k\quad(x\lt k\le j) k(xk≤j) 时这时候期望为 1 j − i 1 ∗ ( d p [ i ] [ k ] 1 ) \dfrac1{j-i1}*(dp[i][k]1) j−i11∗(dp[i][k]1)
那么总的期望为 d p [ i ] [ j ] 1 j − i 1 ∑ k i 1 x − 1 1 j − i 1 ∗ ( d p [ k ] [ j ] 1 ) ∑ k x 1 j − 1 1 j − i 1 ∗ ( d p [ i ] [ k ] 1 ) dp[i][j]\dfrac1{j-i1}\sum_{ki1}^{x-1}\dfrac1{j-i1}*(dp[k][j]1)\\ \sum_{kx1}^{j-1}\dfrac1{j-i1}*(dp[i][k]1) dp[i][j]j−i11ki1∑x−1j−i11∗(dp[k][j]1)kx1∑j−1j−i11∗(dp[i][k]1) 1 j − i 1 ∗ ( 1 ∑ k i 1 x − 1 ( d p [ k ] [ j ] 1 ) ∑ k x 1 j − 1 ( d p [ i ] [ k ] 1 ) ) \dfrac1{j-i1}*(1\sum_{ki1}^{x-1}(dp[k][j]1)\sum_{kx1}^{j-1}(dp[i][k]1)) j−i11∗(1ki1∑x−1(dp[k][j]1)kx1∑j−1(dp[i][k]1))
这里没有把求和符号中的 1 1 1 那个部分单独拆出来是因为 i 1 i1 i1 与 x − 1 x-1 x−1 以及 x 1 x1 x1 与 j − 1 j-1 j−1 的大小关系不明确有可能 i 1 x − 1 i1\lt x-1 i1x−1 也有可能 i 1 x − 1 i1\gt x-1 i1x−1直接拆出来不知道有几个 1 1 1。
回到正题这个式子我们正常算的时候需要枚举左右端点和枚举 k k k是 O ( n 3 ) O(n^3) O(n3) 的但是题目要求是 O ( n 2 ) O(n^2) O(n2)的那么如何优化这个式子呢如果我们把 d p [ k ] [ j ] 1 dp[k][j]1 dp[k][j]1 这个部分看成一个整体发现当 j j j 固定的时候它相当于一个前缀和。同理当 i i i 固定的时候 d p [ i ] [ k ] 1 dp[i][k]1 dp[i][k]1 也相当于一个前缀和。
那么怎么边算边记录这个前缀和呢假设我们第一维枚举 i i i第二维枚举 j j j那么我们第二维在枚举 j j j 的时候 i i i 就是固定的用一个变量记录 s i k ∑ k x 1 j − 1 ( d p [ i ] [ k ] 1 ) s_{ik}\sum_{kx1}^{j-1}(dp[i][k]1) sik∑kx1j−1(dp[i][k]1) 即可。而 ∑ k i 1 x − 1 ( d p [ k ] [ j ] 1 ) \sum_{ki1}^{x-1}(dp[k][j]1) ∑ki1x−1(dp[k][j]1) 这个前缀和看似不好处理实际上我们对每个 j j j 单独开一个变量来记录就可以了具体来说就是用 s k j [ j ] ∑ k i 1 x − 1 ( d p [ k ] [ j ] 1 ) s_{kj}[j]\sum_{ki1}^{x-1}(dp[k][j]1) skj[j]∑ki1x−1(dp[k][j]1)。
这题我一开始其实是从区间 [ 1 , n ] [1,n] [1,n] 为起点开始推的但是从 [ i , j ] → [ 1 , n ] [i,j]\rightarrow[1,n] [i,j]→[1,n] 的期望和 [ i , j ] → x [i,j]\rightarrow x [i,j]→x 的期望不是一回事两者不能直接互通导致想法假了赛时被单防。不能给新生一点小小的acm震撼真是太可惜了。
code
#include iostream
#include cstdio
using namespace std;
typedef long long ll;
const int maxn5005;
const ll mod998244353;ll qpow(ll a,ll b){b%mod-1;ll basea%mod,ans1;while(b){if(b1){ans*base;ans%mod;}base*base;base%mod;b1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);}int n,x;
ll f[maxn][maxn];
ll skj[maxn],sik;int main(){cinnx;for(int ix;i1;i--){sik0;for(int jx;jn;j){f[i][j](1llskj[j]sik)*inv(j-i1)%mod;skj[j](skj[j]f[i][j]1)%mod;sik(sikf[i][j]1)%mod;}}coutf[1][n]endl;return 0;
}H.抽卡记录
题面 思路
魔王题之一。
如果去除掉变化至多 k k k 次的限制条件这个题就是个裸的 L I S LIS LIS 最长上升子序列问题。加上 k k k 次的限制条件就在原来的基础上多加一维其实就可以了要界定最后是上升段还是下降段就再加一维这本质还是 L I S LIS LIS 问题。经验还是不足。
具体来说设 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1] 表示前 i i i 个数以第 i i i 个数结尾也就是必选第 i i i 个数变化了 j j j 次最后一段是在上升段还是下降段的最少删除次数。
转移的话就是枚举 1 ∼ i − 1 1\sim i-1 1∼i−1 尝试由前面的某个位置转移过来。转移方法看代码。
code
#include iostream
#include cstdio
using namespace std;
const int maxn1005;
const int maxk15;
const int inf1e9;int n,m,a[maxn];
//前i个数变化k次现在向上/下变化的最小删除次数
int dp[maxn][maxk][2];int main(){cinnm;for(int i1;in;i)cina[i];for(int i0;in;i)for(int j0;jm;j)for(int k0;k1;k)dp[i][j][k]inf;for(int i1;in;i){dp[i][0][0]dp[i][0][1]i-1;for(int ji-1;j1;j--){for(int k0;km;k){if(a[i]a[j]){dp[i][k][0]min(dp[i][k][0],dp[j][k][0]i-j-1);if(k0)dp[i][k][0]min(dp[i][k][0],dp[j][k-1][1]i-j-1);}else if(a[i]a[j]){dp[i][k][1]min(dp[i][k][1],dp[j][k][1]i-j-1);if(k0)dp[i][k][1]min(dp[i][k][1],dp[j][k-1][0]i-j-1);}else continue;}}}int ansn-1;for(int i1;in;i)for(int k0;km;k)ansmin(ans,min(dp[i][k][0],dp[i][k][1])n-i);coutn-ans;return 0;
}I.安达的二维矩阵
题面 思路
签到题。读入第 i i i 行的时候顺便数一下当前行有多少个 1 1 1另外设置两个变量分别记录之前 1 1 1 最多的行的编号和 1 1 1 的个数如果第 i i i 行的 1 1 1 个数更多就转而记录第 i i i 行的信息。
code
#include iostream
#include cstdio
using namespace std;int n,m;int main(){cinnm;int x1,y0;for(int i1,t;in;i){int cnt0;for(int j1;jm;j){cint;if(t1)cnt;}if(cnty)xi,ycnt;}coutx y;return 0;
}J.安达的数字手术
题面 思路
如果是正常的删除某一个数位上的数这个数的数位会减少 1 1 1但是如果删除第一位的时候能出现前导零就可以删掉多位数因此如果删第一位能出现前导零从而删掉多位就删第一位就行了。
但是如果不是这种情况考虑如何删数能使得数字最小数位相同时其实就是字典序最小发现其实我们删数的时候就是把第 i i i 位的数删掉然后把第 i 1 i1 i1 位的数放到第 i i i 位上后面依次向前补。因此我们删数的时候一定删那种第 i i i 位上的数大于第 i 1 i1 i1 位上的数这样后面数位向前补的时候第 i i i 位才会变得更小。因为是字典序最小只要高位更小整个串就最小。因此我们贪心地找到第一个 第 i i i 位上的数大于第 i 1 i1 i1 位上的数 的位置删掉它就行了。找到最后都没找到的话就删掉最后一位。
code
#include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;int n;
string s;bool lt(string a,string b){if(a.size()!b.size())return a.size()b.size();else return ab;
}int main(){cinns;if(n1){cout0endl;return 0;}string t,t2;int idx1;while(idxn s[idx]0)idx;ts.substr(idx);if(!t.size())t0;for(int i1;in;i){if(i1n s[i]s[i1]){t2s.substr(0,i)s.substr(i1);break;}}if(!t2.size())t2s.substr(0,n-1);if(lt(t,t2))coutt;else coutt2;return 0;
}K.跳楼梯
题面 思路
一开始我也往 B F S BFS BFS 上想了但是发现太过复杂有可能需要访问负的下标正的下标也可能超过 n n n。翻一下榜发现 A A A 掉这题的人有过的很快的这说明这个题的码量和书写的难度并不大所以直接尝试推结论几分钟就出了。
这个题其实就相当于是选取等差数列上的某几个数改成 − 1 -1 −1使得它们的和等于 n n n。首先罗飞云要到达第 n n n 层首先你等差数列的总和必须得不小于 n n n这样你把某些数改成 − 1 -1 −1 的时候总和会变小它才有可能等于 n n n。
发现正因为是等差数列它有一个很优美的性质就是我们只选择一个数变成 − 1 -1 −1 的话从 1 1 1 到 x x x总和会在原来的基础上减少 2 , 3 , 4 , … , x 1 2,3,4,\dots,x1 2,3,4,…,x1。如果我们找到第一个 x x x 使得 1 ∼ x 1\sim x 1∼x 的和 t o t tot tot 大于等于 n n n这时只要 t o t tot tot 和 n n n 相差不为 1 1 1我们就可以从 1 ∼ x 1\sim x 1∼x 找到一个数把总和减少到 n n n。
这是因为 t o t − x tot-x tot−x 相当于 1 ∼ x − 1 1\sim x-1 1∼x−1 的和根据我们上面 x x x 是第一个 使得 1 ∼ x 1\sim x 1∼x 的和 t o t tot tot 大于等于 n n n 的位置 的前提也就是 t o t − n x tot-n\lt x tot−nx 如果 t o t − n ≥ 2 tot-n\ge 2 tot−n≥2 我们就一定能找到这个差值继而找到变成 − 1 -1 −1 的那个数这时答案就是 x x x。而当 t o t n totn totn 的时候答案就是 x x x当 t o t − n 1 tot-n1 tot−n1 时必须额外补一个 − 1 -1 −1这时答案就是 x 1 x1 x1。
这个 x x x 的计算可以二分来算。直接暴力枚举 O ( t n ) O(t\sqrt{n}) O(tn ) 也不会超时。
code
#include iostream
#include cstdio
#include queue
using namespace std;
const int maxn1e65;int T,n;int main(){cinT;while(T--){cinn;int l1,r2000,mid;while(lr){mid(lr)1;if(mid*(mid1)/2n)rmid;else lmid1;}if(l*(l1)/2-n1)coutl1endl;else coutlendl;}return 0;
}L.前缀和
题面 思路
就是算前缀和然后二分查询题面问的很直白了。不过这题卡cin需要取消同步或者改用scanf。
code
#include iostream
#include cstdio
#include algorithm
using namespace std;
typedef long long ll;
const int maxn1e65;int n,Q;
ll s[maxn],sum;int main(){ios::sync_with_stdio(false);cin.tie(0); cinnQ;for(int i1;in;i){cins[i];s[i]s[i-1];}while(Q--){cinsum;if(sums[n])cout-1\n;else cout(lower_bound(s1,sn1,sum)-s)\n;}return 0;
}
