没想到我竟然能有幸成为参加noip2020中7k+人的一员话说不是有分就能去的吗今天考完了，特地来写个小结
虽然在考完csp后并不认为我能参加noip，但我还是去机房参加训练（毕竟万一进了不是很亏？）在得知noip有分就行的消息后，我更加努力地准备腐
于是在洛谷上做了一些题。为什么是做了一些题呢？因为我太菜了，做一道题都要很久QAQ。到了比赛前没有奥赛课的时候，我看那些高三大佬都翘课来准备，于是我周三周四的晚修请假来机房训练（还不敢翘课）。在这两个晚上，我着重搞了搞之前鸽了很久都快忘了的算法，包括但不限于线段树，树链剖分，并查集，最小生成树，最短路，倍增LCA（主要是我也忘了我搞了啥）
这里有一点经验，就是在学算法的时候不要看别人的代码，自己按照思路写印象会更深刻，捡起来也会更快。还有，写板子但时候一定要打上完备的注释（我基本一行一个），这样每次只要看看注释就知道自己当时在想什么了。最好还能有自己的blog，当然用markdown渲染也行。
最令人惊讶的是有一位大佬竟然在进场的时候前提到了gcd！然后我才发现我在准备的时候忘记搞gcd了！这波要是他不提一下我t1就凉了，妙啊！说的好像t1没凉一样
来自大佬的gcd超短模板
cppll gcd(ll a,ll b)
{
return b? gcd(b,a%b):a;
}
上来一眼看到还以为是网络流！真是骇死我了。。。。。。
然后瞎写了一阵，把样例打进去，咦？怎么输入还没完就输出答案了？才发现还有中间节点QAQ
于是删掉重来，一开始就想到了bfs，但是STL的queue不会用，主要是不知道怎么取出队头。。。。。。那就手写吧！于是手写了top，empty，push和pop。
cppint que[1000010];
int front=0;int tail=0;
int top()
{
return que[front];
}
void pop()
{
if(front<tail) front++;
}
void push(int a)
{
que[tail++]=a;
}
bool empty()
{
return front==tail;
}
然后又写了个分数的结构体，用构造函数初始化分母为1。由于之前重载运算符写吐了，这次直接就写了两个函数，一个搞加法，一个搞除法。
然而一输样例，发现竟然输出了负数！于是把int 改了ll，问题依旧。后来把通分时算lcm先乘后除就好了。
cppstruct fen
{
ll up;
ll down;
fen()
{
down=1;
}
};
fen add(fen &a,fen b)
{
ll g=gcd(a.down,b.down);
ll lcm=a.down/g*b.down;
a.up*=lcm/a.down;
b.up*=lcm/b.down;
a.up+=b.up;
a.down=lcm;
g=gcd(a.up,a.down);
a.up/=g;
a.down/=g;
return a;
}
void chu(fen &a,int b)
{
a.down*=b;
ll g =gcd(a.up,a.down);
a.up/=g;
a.down/=g;
}
这里要注意一点，这里不只是bfs就行了的，节点要先把水都排进来最后才能排出去，也就是说当一个节点的流入全部算完后才能入队去算流出。这不就是拓扑序嘛。。。。。。emmmm，调的我有亿点久QAQ
cppvoid bfs()
{
while(!empty())
{
int now=top();
pop();
int h=head[now];
fen water;
water.up=out[now].up;
water.down=out[now].down;
chu(water,tot[now]);
while(h)
{
--intot[E[h].to];
add(out[E[h].to],water);
if(!intot[E[h].to]) push(E[h].to);
h=E[h].next;
}
}
}
然而！数据范围是100000而我看成了1000。。。。。。又是一个100变60的伤心故事。。。。。。
ps:猥琐的ccf的猥琐数据的最后一个点爆了unsigned long long!我不觉得有哪个人会在考场上写高精度QAQ
完整代码:
cpp#include<cstdio>
#define ll long long
using namespace std;
ll gcd(ll a,ll b)
{
return b? gcd(b,a%b):a;
}
struct fen
{
ll up;
ll down;
fen()
{
down=1;
}
};
fen add(fen &a,fen b)
{
ll g=gcd(a.down,b.down);
ll lcm=a.down/g*b.down;
a.up*=lcm/a.down;
b.up*=lcm/b.down;
a.up+=b.up;
a.down=lcm;
g=gcd(a.up,a.down);
a.up/=g;
a.down/=g;
return a;
}
ll rd()
{
ll num=0;bool f=false;char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=true;
c=getchar();
}
while(c>='0'&&c<='9')
{
num=(num<<1)+(num<<3)+(c^'0');
c=getchar();
}
if(f) return -num;
else return num;
}
fen out[100010];
ll tot[100010];
struct edge
{
int to;
int next;
}E[101000];
int head[101000];int cnt=0;
void add_edge(int a,int b)
{
E[++cnt].to=b;
E[cnt].next=head[a];
head[a]=cnt;
}
void chu(fen &a,int b)
{
a.down*=b;
ll g =gcd(a.up,a.down);
a.up/=g;
a.down/=g;
}
int que[1000010];
int front=0;int tail=0;
int top()
{
return que[front];
}
void pop()
{
if(front<tail) front++;
}
void push(int a)
{
que[tail++]=a;
}
bool empty()
{
return front==tail;
}
int intot[100010];
void bfs()
{
while(!empty())
{
int now=top();
pop();
int h=head[now];
fen water;
water.up=out[now].up;
water.down=out[now].down;
chu(water,tot[now]);
while(h)
{
--intot[E[h].to];
add(out[E[h].to],water);
if(!intot[E[h].to]) push(E[h].to);
h=E[h].next;
}
}
}
int final[100010];
int Ftot=0;
signed main()
{
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
//int n=rd(),m=rd();
int n,m;
scanf("%d",&n);
scanf("%d",&m);
for(int i=1;i<=n;i++)
{
//tot[i]=rd();
scanf("%lld",&tot[i]);
if(!tot[i]) final[++Ftot]=i;
for(int j=0;j<tot[i];j++)
{
int to;
scanf("%d",&to);
add_edge(i,to);
++intot[to];
}
}
for(int i=1;i<=m;i++)
{
out[i].up=1;
push(i);
}
bfs();
for(int i=1;i<=Ftot;i++)
{
printf("%lld %lld\n",out[final[i]].up,out[final[i]].down);
}
fclose(stdin);
fclose(stdout);
return 0;
}
这种题一看就不会。我估摸着应该是dp，但是这和我不会有什么关系呢？
于是随便写了点东西没思路就走了，最后用半个小时写了只有1个字母的情况。但是复杂度有亿点大。嗯，好问题。。。。。。 关键是这种情况都没写对QAQ
cpp#include<cstdio>
using namespace std;
char s[100010000];
int rdstr()
{
char c=getchar();
while(c<'a'||c>'z') c=getchar();
int len=0;
while(c<='z'&&c>='a')
{
s[len++]=c;
c=getchar();
}
return len;
}
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
int ans=0;
int len=rdstr();
for(int i=1;i<len-1;i++)
{
int left=len-i;
for(int j=1;j<=(left>>1);j++)
{
if(left%j) continue;
int tot=left/j;
for(int k=1;k<tot;k++)
{
if(k%2>i%2) continue;
ans++;
}
}
}
printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}
难得noip竟然考spj！spj都来了，交互题还会远吗？
看到这玩意，第一反应就是不会做。不会做咋办，那就来打个暴力吧。一开始想了一大堆方案，比如从上往下找同色珠子集中到一根柱子上之类的，但都要么不可行，主要是要么不会写。到最后，想到要是能交换两根柱子上的任意两个珠子就好了。我盲猜用一根空的柱子是可以的，于是开始研究，最后还真给研究出来了！
首先先确定两颗珠子的深度大小关系,防止下面操作的时候爆柱子
cppif(i>j) //i<j
{
int c=b;
b=a;
a=c;
c=j;
j=i;
i=c;
}
然后把深度大的那一串(a)连带着要移动的那一颗移到空柱子上
cppfor(int k=tot[a];k>=i;k--)//a:i~top to empty
{
//printf("%d %d\n",a,empty);
mem(a,empty);
tot[a]--;
stick[empty][++tot[empty]]=stick[a][k];
++atot;
}
然后把深度小的那一串(b)连带着要移动的那一颗移到刚刚移走一串的那根柱子(a)上.由于a上移走的那一串要比这一串多,所以不会爆出柱子
cppfor(int k=tot[b];k>=j;k--)//b:j~top to a
{
//printf("%d %d\n",b,a);
mem(b,a);
tot[b]--;
stick[a][++tot[a]]=stick[b][k];
++btot;
}
然后我们就可以把原本属于a的那一颗移到b上.柱子类似栈,移动完是倒序的,所以刚刚要交换的两颗珠子现在都到了最上面
cpp//printf("%d %d\n",empty,b);//empty: top to b
mem(empty,b);
stick[b][++tot[b]]=stick[empty][tot[empty]--];
--btot;
然后就要把刚刚从b上移走的那一串还回来,当然,要移到a上的那一颗先放到empty上.由于empty刚刚移走了一颗,这样做仍然不会爆柱子
cpp//printf("%d %d\n",a,empty);//a:top to empty
mem(a,empty);
stick[empty][++tot[empty]]=stick[a][tot[a]--];
for(int k=0;k<btot;k++)//a:j~top to b
{
//printf("%d %d\n",a,b);
mem(a,b);
stick[b][++tot[b]]=stick[a][tot[a]--];
}
这样做完,a上要移动到的那个位置就暴露出来了,把empty上的东西移动回来就可以了
cppfor(int k=tot[empty];k>0;k--)//empty to a
{
//printf("%d %d\n",empty,a);
mem(empty,a);
stick[a][++tot[a]]=stick[empty][tot[empty]--];
}
然后主程序就简单了,不妨认为一根柱子最下面的那一颗是这跟柱子的颜色(反正题目也没规定),前面的柱子都移动好了,从上往下一旦遇到不一样颜色的珠子,就在后面的柱子上找一个颜色一样的交换一下就行了
cppfor(int i=1;i<n;i++)
{
int k=i+1;
int l=m;
for(int j=2;j<=m;j++)
{
if(stick[i][j]==stick[i][1]) continue;
for(;k<=n;k++)
{
bool flag =false;
if(!l) l=m;
for(;l>0;l--)
{
if(stick[k][l]==stick[i][1])
{
change(i,j,k,l);
flag=true;
break;
}
}
if(flag) break;
}
}
}
但是由于复杂度太大，经过了不懈随意地卡常，大样例还是跑了1.4s，不过还好答案是对的,最后骗到了40分。
完整代码:
cpp#include<cstdio>
using namespace std;
int stick[60][410];
int tot[60];
int empty;
int ans1[820010],ans2[820010];
int cnt=0;
void mem(int a,int b)
{
ans1[++cnt]=a;
ans2[cnt]=b;
}
int rd()
{
int num=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
{
num=(num<<1)+(num<<3)+(c^'0');
c=getchar();
}
return num;
}
void change(int a,int i,int b,int j)//change a[i] and b[j]
{
if(i>j) //i<j
{
int c=b;
b=a;
a=c;
c=j;
j=i;
i=c;
}
int atot=0,btot=0;
for(int k=tot[a];k>=i;k--)//a:i~top to empty
{
//printf("%d %d\n",a,empty);
mem(a,empty);
tot[a]--;
stick[empty][++tot[empty]]=stick[a][k];
++atot;
}
for(int k=tot[b];k>=j;k--)//b:j~top to a
{
//printf("%d %d\n",b,a);
mem(b,a);
tot[b]--;
stick[a][++tot[a]]=stick[b][k];
++btot;
}
//printf("%d %d\n",empty,b);//empty: top to b
mem(empty,b);
stick[b][++tot[b]]=stick[empty][tot[empty]--];
--btot;
//printf("%d %d\n",a,empty);//a:top to empty
mem(a,empty);
stick[empty][++tot[empty]]=stick[a][tot[a]--];
for(int k=0;k<btot;k++)//a:j~top to b
{
//printf("%d %d\n",a,b);
mem(a,b);
stick[b][++tot[b]]=stick[a][tot[a]--];
}
for(int k=tot[empty];k>0;k--)//empty to a
{
//printf("%d %d\n",empty,a);
mem(empty,a);
stick[a][++tot[a]]=stick[empty][tot[empty]--];
}
}
int main()
{
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
int n=rd(),m=rd();
//scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
tot[i]=m;
for(int j=1;j<=m;j++)
{
//scanf("%d",&stick[i][j]);
stick[i][j]=rd();
}
}
empty=n+1;
for(int i=1;i<n;i++)
{
int k=i+1;
int l=m;
for(int j=2;j<=m;j++)
{
if(stick[i][j]==stick[i][1]) continue;
for(;k<=n;k++)
{
bool flag =false;
if(!l) l=m;
for(;l>0;l--)
{
if(stick[k][l]==stick[i][1])
{
change(i,j,k,l);
flag=true;
break;
}
}
if(flag) break;
}
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
printf("%d %d\n",ans1[i],ans2[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}
这是人能做的题吗？输-1拿5分就回去调t1去了最后发现骗到了十分
cpp#include<cstdio>
using namespace std;
int main()
{
freopen("walk.out","w",stdout);
printf("-1");
fclose(stdout);
return 0;
}
训练的时候，写完快读突发奇想
众所周知在main函数外面是不能执行函数的，但是把函数的返回值赋给变量竟然还就可以了！
至于怎么结束程序不re,不是可以用exit(0)嘛~
甚至都不需要main函数，有个main数组或是main指针竟然还能顺利通过编译！
感受一下不用main就能执行的a+b(虽然洛谷上会CE)
本文作者:GBwater
本文链接:
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！