posted on 2021-10-03 11:22:24 | under 学术 | source
哇，这个 SB 怎么这么喜欢挂分。
不行，要记录一下是怎么挂分的，防止 CSP-J/S 挂分。<= 年少无知，应该是防止丢掉提高一等
41
bool check(int j,const char*a){
int m=strlen(a+1);
// ^~~
for(int i=0;i<m;i++){
if(s[i+j]!='?'&&s[i+j]!=a[i]) return 0;
}
return 1;
}
if(check(i+1,"sakana"))
下标人属于是
40
近日有出题人使用模数 \(998244{\color{red}8}53\) 导致 100->10 距今 0 天警钟长鸣
近日有出题人使用模数 \(99{\color{red}3}244353\) 导致 ?->? 距今 0 天警钟长鸣
39
喜报：近日广东一考生竟反向容斥（斥容），WA on test 9，距今一天，警钟长鸣
for(int i=m;i>=1;i--){
for(LL j=1;j*j<=i;j++){
if(i%j==0){
if(i!=j) l[i]=(l[i]-l[j]+P)%P;
if(i/j!=j&&j!=1) l[i]=(l[i]-l[i/j]+P)%P;
}
}
}
注解：\(l_i={\tt constant}-\sum_{j|i,j<i}l_j\) 的容斥，正确写法为：
for(int j=1;j<=m;j++){
for(int i=j+j;i<=m;i+=j) l[i]=(l[i]-l[j]+P)%P;
}
for(int i=1;i<=m;i++){
for(int j=1;j*j<=i;j++){
if(i%j==0){
if(i!=j) l[i]=(l[i]-l[j]+P)%P;
if(i/j!=j&&j!=1) l[i]=(l[i]-l[i/j]+P)%P;
}
}
}
38
喜报：近日……乘法不开 LL，……警钟长鸣
for(int i=1;i<=m;i++) f[i]=qpow(i*(i+1)/2,n);
//m<=1e5
37
喜报：近日广东一考生试图用 scanf("%1d") 输入 \(4\times 10^6\) 个 0/1 数字，卡成暴力，距今 1min，警钟长鸣
注：被卡常了
36
喜报：近日广东一考生在模拟赛中使用如下代码，整题 RTE，距今 1h，警钟长鸣
LL f[510][200010];
//注：空间 700 MB
喜报：近日广东一考生在 4h 的模拟赛中冲了 2h 的 D，最终直接爆零，距今 2h，警钟长鸣
35
SS @NobodyThere 提高 T2 编译错误 警钟长鸣
#define positive [](int x){return x>0;}
void init(bool lim(int x)){
puts("compile error");
}
init(positive);
#include <functional>
void init(std::function<bool(int)> lim){
puts("Accepted");
}
init(positive);
考场 Dev-c++ 能过编译。
34
LL dp(){
for(int i=1;i<=n;i++) f[i]=1e18;
for(int i=n+1;i<=n*2;i++) f[i]=-1e18;
for(int i=1;i<=n;i++) if(!deg[i]) q.push({f[i],i});
for(int i=n+1;i<=n*2;i++) if(!deg[i]) f[i]=0,expand(i);
//...
}
\(f_i\) 没有初始化！
有的时候发现写出来的代码没过样例，一种可能是写挂了（代码问题），一种可能是你假掉了（你的问题），一般是前者呢
33
LL solve2(int l,int r){
// f[l-1]=0;
// LL res=0;
// for(int i=l;i<=r;i++){
// f[i]=(a[i]*(f[i-1]+1)+(1-a[i])*f[i-1]%P*T)%P;
// //f[i]=a[i]*f[i-1]+a[i]-a[i]*f[i-1]*T+f[i-1]*T
// // =f[i-1]*(a[i]-a[i]*T+T)+a[i]
// res=(res+(f[i-1]+1)*a[i])%P;
// }
// return res;
return ((f0*ccf.query(l,r))[0][1]+t.query(r)-t.query(l-1))%P;
}
看到那个 \(1-a[i]\) 了吗？减爆了，没取模，样例过不了，而开始怀疑算法正确性。
32
void dp(){
f[0][0][0]=1;
for(int i=1;i<=n*2;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=n*(n-1)/2;k++){
f[i&1][j][k]=((f[(i^1)&1][j-1][k]+g[(i^1)&1][j+1][k])%P-g[(i^1)&1][j+1][k-j-1]+P)%P;
// printf("f[%d][%d][%d]=%d\n",i,j,k,f[i][j][k]);
}
g[i&1][j][0]=f[i&1][j][0];
for(int k=1;k<=n*(n-1)/2;k++) g[i&1][j][k]=(g[i&1][j][k-1]+f[i&1][j][k])%P;
}
}
}
\(k-j-1\) 会越界的呢
31
李超线段树，写不写等号都可以，但是
void insert(func<T> f,int p,int l,int r){
int mid=(l+r)>>1;
switch((tag[p](l)<=f(l))+(tag[p](r)<=f(r))){
case 2: tag[p]=f; break;
case 1: insert(f,p<<1,l,mid),insert(f,p<<1,mid+1,r);break;
}
}
注意第二个 insert 传的 p
30
29
复杂度分析：分治，\(<B\) 的 \(O(c^{\color{red}3})\)，\(\geq B\) 的 \(O(n)\)，那么请问你的复杂度是 \(B=\sqrt{n},O(n^{1.5})\) 吗？？？
\(\sqrt[3]{\quad}\) 分治？？？真就严格优于暴力
28
试图在 cmd 中输入 color 以运行 color.exe
正确做法：color.exe 或 .\color
27
26
25
dfs 找环！
void dfs(int u,int fa=0){
if(vis[u]){
h[++cnt]=u;
while(stk[top]!=u) h[++cnt]=stk[top--];
reverse(h+1,h+cnt+1);
return ;
}
vis[stk[++top]=u]=1;
for(int i=t.head[u];i;i=t.nxt[i]){
int v=t[i].v; if(v==fa) continue;
// ^~~~~~~~~~~~~~~~~~~
dfs(v,u);
if(cnt) return ;
}
}
void dfs(int u){
if(vis[u]){
h[++cnt]=u;
while(stk[top]!=u) h[++cnt]=stk[top--];
reverse(h+1,h+cnt+1);
return ;
}
vis[stk[++top]=u]=1;
for(int i=t.head[u];i;i=t.nxt[i]){
int v=t[i].v;
dfs(v);
if(cnt) return ;
}
}
有向基环树，从一个点出发保证进环。
哪个是对的捏？是第二个，因为你考虑
2 2
1 2
2 1
显然有一个环 \(1\Leftrightarrow 2\)，但是因为 v!=fa 的限制，寄了！
其实为什么不用 toposort 呢？
24
//matrix<N,1,int> r;
template<int N> matrix<N,1> operator+(matrix<N,1> &a,matrix<N,1> &b){
matrix<N,1> r;
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
r[i][1]=(r[i][1]+1ll*a[(i-k+n)%n+1][1]*b[k][1]%P);
return r;
}
一个括号，一个保龄，今天你溢出了吗
23
22
T dinic(int s,int t,T inf=1e9){
T flow=0;
while(bfs(s,t)) flow+=dinic(s,inf,t);
return flow;
}
递归函数
21
20
19
18
廊桥分配：当你发现二分没有单调性时，试试滑动窗口
廊桥分配送我退役！
17
对着 \(k\leq n\leq 10^5\) 想了很久，结果 \(k\leq 50\)
16
FHQ-treap 的合并需要保证相对顺序，就是说，只能合并程序分裂的 treap
15
交互：询问次数 \(2n\) 一上来就询问 \(n\) 次
14
13
12
LL a[100010];
int del=a[i]-a[i-1];
数据没保证啊
11
“\(n,m\leq 2000\)”
int a[1010][1010]
10
#include <cmath>
/tmp/compiler_2b2px1fj/src: 在函数‘int main()’中:
/tmp/compiler_2b2px1fj/src:50:17: 错误：‘sqrt’在此作用域中尚未声明
50 | int k=pri[i]<=sqrt(n)?0:(pri[i]*3>n)+1;
| ^~~~
#include <vector>
/tmp/compiler_tz_45o8w/src:10:1: 错误：‘vector’不是一个类型名
10 | vector<int> s[1000010];
| ^~~~~~
/tmp/compiler_tz_45o8w/src: 在函数‘int check()’中:
/tmp/compiler_tz_45o8w/src:15:27: 错误：‘s’在此作用域中尚未声明
15 | for(;pos<=n;pos++) if(s[pos].size()<2) break;
| ^
/tmp/compiler_tz_45o8w/src:16:9: 错误：‘s’在此作用域中尚未声明
16 | if(!s[pos].size()) pos--;
| ^
/tmp/compiler_tz_45o8w/src:17:16: 错误：‘s’在此作用域中尚未声明
17 | assertf(1<=s[pos].size()&&s[pos].size()<=2);
| ^
/tmp/compiler_tz_45o8w/src: 在函数‘int main()’中:
/tmp/compiler_tz_45o8w/src:29:50: 错误：‘s’在此作用域中尚未声明
29 | for(int i=1;i<=n;i++) assertf(dis[i]<=n),s[dis[i]].push_back(i);
| ^
/tmp/compiler_tz_45o8w/src:33:32: 错误：‘s’在此作用域中尚未声明
33 | printf("%d %d 1\n",s[i][0],s[i+1][0]);
| ^
/tmp/compiler_tz_45o8w/src:38:12: 错误：‘s’在此作用域中尚未声明
38 | if(s[pos].size()>1) printf("%d %d 1\n",s[pos][0],s[pos][1]);
| ^
/tmp/compiler_tz_45o8w/src:42:40: 警告：格式 ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘LL’ {aka ‘long long int’} [-Wformat=]
42 | for(int i=1;i<=n;i++) printf("%d\n",dis[p[i]]);
| ~^ ~~~~~~~~~
| | |
| int LL {aka long long int}
| %lld
缺省源警告
9
线段树特判 \(ql>qr\) 等一系列离谱情况。
8
删调试信息。这种情况，可以在本地编译命令加个 -DLOCAL，然后写个宏定义：
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...)
#endif
7
LL f(int x){
return 1ll*x*(x-1)/2;
}
int res=f(114514);
搁着 int 接 LL
6
int d=-114515;
if(d%2==1) printf("odd");
else printf("even");
热知识：-3%2==-1！
int mod(int x,int p=P){return (x%p+p)%p;}
5
int maxx(int a,int b){return a>b?b:a;}
// ^
你 \(\max\) 你妈呢
4
template<int N> struct dsu{
int fa[N+10],size[N+10],cnt;
dsu():cnt(N){for(int i=1;i<=N;i++) fa[i]=i;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
bool query(int x,int y){return find(x)==find(y);}
void merge(int x,int y){
int tx=find(x),ty=find(ty);
// ^
if(tx!=ty){
fa[ty]=tx;
size[tx]+=size[ty];
}
}
};
自己使用自己
3
int n,m;
graph<100010,300010> g,t;
bool vis[300010];
dsu<100010> s;
int kruskal(){
int ans=0;
for(int i=1;i<=g.cnt;i++){
if(!s.query(g[i].u,g[i].v)){
vis[i]=1;
ans+=g[i].w;
s.merge(g[i].u,g[i].v);
t.link(g[i].u,g[i].v,g[i].w);
}
}
return ans;
}
请您的 Kruskal 排序
2
void dijkstra(int s,int dis[]){
priority_queue<node,vector<node>,greater<node> > q;
memset(dis,0x3f,sizeof dis);
// ^~~~~~~~~~
memset(vis,0,sizeof vis);
dis[s]=0,q.push(node(0,s));
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v,w=g[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(node(dis[v],v));
}
}
}
}
此处 dis 是个指针，int* 的那种，对这个指针取 sizeof，结果是这个指针所占空间大小，而不是这个 SB 想要的 dis 的空间。
两种解决方法：
- 在外面
memset(dis,0x3f,sizeof dis)，一劳永逸； memset(dis,0x3f,sizeof(int)*(n+1))，注意是 \(\times (n+1)\)。
1
对拍的时候不要重定义两次文件输入输出，慎防 fc 空文件。
解决方法：看一眼。
标签：cnt,return,vis,int,LL,错题,dis From： https://www.cnblogs.com/caijianhong/p/error-book.html