原题解链接：https://ac.nowcoder.com/discuss/149990 东西:形状和排列顺序。先来看形状如何确定:题目里定义"连续的1序列”是不拐弯的，也就是说最优的答案一定会被两种摆放方式包含: 1:全横着放。 2:全竖着放。 我们先考虑全横着放的情况，竖着同理。对于全横着放的矩阵一共有444行， 由于序列不拐弯，所以分开考虑他们，最后取max即可。理(gan)性(xing)思(li)考(jie)一下一个作为答案的序列是什么样子的，显然它由三部分构成一个矩阵的后缀111数列(可以没有) , t(t>=0)t(t >= 0)t(t>=0)个这行全为111的矩...

原题解链接：https://ac.nowcoder.com/discuss/149990 由题可知，如果该序列均为非负数,则从左向右依次删除最优,代价为各个数之和。 而序列中如果有负数,则先从右向左依次删除每个负数，这样会使代价减小的最多。然后序列就只剩下了非负数,依次删除即可。 #include <bits/stdc++.h> using namespace std; int n; long long ans, x; int main() { scanf("%d", &n); for(int i = 1 ; i <= n ; ++ i) scanf("%lld", ...

原题解链接：https://ac.nowcoder.com/discuss/149984 首先可以装压dp 令f(i,j)f(i,j)f(i,j)表示由合法状态i转移到合法状态jjj的方案数 对于合法的状态我们可以dfsdfsdfs出来 对于状态转移间连边,发现对于状态之间的转移是一个有向图, 那么题目就抽象成了对于一个有向图,求从任意点出发，转移nnn次的形成的环的总数 这个显然可以floyedfloyedfloyed转移的 那么只需要对于状态的邻接矩阵进行做nnn次方,然后对于每个点出发的状态方案计数,也就是对矩阵对角线上的值求和 // luogu-judger-enable-o2 #in...

原题解链接：https://ac.nowcoder.com/discuss/149984 idk(n)=nK,μ(n)i d k(n)=n^{K}, \mu(n)idk(n)=nK,μ(n) 为积性函数 其中 idk(x)i d k(x)idk(x) 为完全积性函数 发现这个式子为这两个函数的狄利克雷卷积,那么 F(x)F(x)F(x) 也是一个积性函数考虑进行线性简 若 (a,b)=1(a, b)=1(a,b)=1 那么 F(ab)=F(a)∗F(b)F(a b)=F(a) * F(b)F(ab)=F(a)∗F(b) 若 (a,b)!=1(a, b) !=1(a,b)!=1 考虑只一个质数 ...

原题解链接：https://ac.nowcoder.com/discuss/149984 首先发现 如果选出来的那一部分匹配的话,那么剩下的也一定匹配 那么问题就是求括号匹配序列的方案 设dp[i][j]dp[i][j]dp[i][j]表示前iii个括号,选取序列左括号比右括号多了jjj个 那么转移就好写了 f[i][j]=f[i−1][j+−1]+f[i][j]f[i][j]=f[i-1][j+-1]+f[i][j]f[i][j]=f[i−1][j+−1]+f[i][j] 枚举jjj转移然后滚掉一维 #include <cstdio> #include <cmath>...

原题解链接：https://ac.nowcoder.com/discuss/149984 本场饲喂量小的题目 发现从xxx出发,只有一条路径可以只经过一次，其他的都会经过两次 找出这条最长的路径,用所有路径权值之和*2，减去这条路径的就好了 #include<bits/stdc++.h> using namespace std; inline int read() { int x = 0,f= 1; char c = getchar(); while(c < '0' || c > '9')c = getchar(); while(c <= '9' &&am...

原题解链接：https://ac.nowcoder.com/discuss/150007 做法一： 本题数据范围较小，可以直接暴力遍历所有日期。 做法二： 打表  #include <iostream> #include <cstdio> #include <cstring> using namespace std; struct date{ int year; int morth; int day; }; int daymap[]={0,31,28,31,30,31,30,31,31,30,31,30,31}; date add(date &x){...

原题解链接：https://ac.nowcoder.com/discuss/150007 暴力 #include <bits/stdc++.h> #define LL long long using namespace std; const int maxn=2e5+10; int n,m; char s[310][2][3010]; int comfort(char *sr,char*s1) { int f=s1[0]=='-'; if(f)s1++; for(int i=0;sr[i];i++) { int j; for(j=0;s1[j];j++) if(s1[j]==sr[...

原题解链接：https://ac.nowcoder.com/discuss/150007 暴力 #include<cstdio> #include<cstdlib> #include<cstring> #define int long long using namespace std; const int maxn=10010; int n,en,cnt[maxn][2]; struct edge { int e,d; edge *next; }*v[maxn],ed[1001000]; void add_edge(int s,int e,int d) { ...

原题解链接：https://ac.nowcoder.com/discuss/150007 暴力  #define _CRT_SECURE_NO_DEPRECATE /************************ *创建时间：2018 09 14 *文件类型：源代码文件 *题目来源：原创题 *当前状态：已通过 *备忘录：最大匹配关键边 标程 *作者：HtBest ************************/ #include <stdio.h> #include <iostream> #include <string> #include <st...

原题解链接：https://ac.nowcoder.com/discuss/150009 从地图边界开始DFSDFSDFS，在不经过#的情况下所能到达的所有点都是不合法的。那么记能到达的点数为cntcntcnt，答案即为nxm−cntnx m- cntnxm−cnt。 注意所有的#都是要被计人答案的。故DFSDFSDFS的起点不能是#。  #include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <time.h> #inc...

原题解链接：https://ac.nowcoder.com/discuss/150009 打表发现，对于n≥2n≥2n≥2,都是先手赢。 Winning. Ways.for. Your.Mathematical.Plays. V1 Chapter 7, P193中有对FusionPrincipleFusion PrincipleFusionPrinciple的证明，由此证明本题。 下面是FusionPrincipleFusion PrincipleFusionPrinciple的简要说明: 给出一个无向图和一个起点，AliceAliceAlice和BobBobBob在其上玩删边游戏,它的SGS...

原题解链接：https://ac.nowcoder.com/discuss/150009 本题有多种做法。这里介绍一种奇特的做法。 首先离线,将所有出现值离散化。再用权值线段树维护当前兵力值序列中最左和最右的兵力值大于等于数vvv的位置,分别记为lv,rvl_{v}, r_{v}lv​,rv​。考虑到兵力值序列一定是一个上凸的序列，所以整个序列中兵力值大于等于某个数的数的个数就是rv−lv+1r_{v}-l_{v}+1rv​−lv​+1，回答询问时将左右端点限制在询问区间内即可。 查询整个序列的和只要对每一段Δv\Delta vΔv求其出现次数，相乘就是这一段Δv\Delta vΔv的贡献。全...

原题解链接：https://ac.nowcoder.com/discuss/150009 这里介绍一种可行的构造方法。首先在点(n,1)(n,1)(n,1)与(n−3,0)(n-3,0)(n−3,0)之间连一条线，之后依次连接(n,min(1+2k,n))(n, min(1 + 2k,n))(n,min(1+2k,n))与(max(n−3−2k,0),0),(k∈Z,k>0)(max(n-3- 2k,0),0), (k∈Z,k>0)(max(n−3−2k,0),0),(k∈Z,k>0)直至1+2k≥n1+2k≥n1+2k≥n并且n−3−2k≤0n-3-2k≤0n−3−2k≤0...