noip模拟赛沙雕总结 18.9.11

沙雕总结 18.9.11"/>

noip模拟赛沙雕总结 18.9.11

额。。考了两个点，估分150，实际95，看来自己代码水平还有很多进步的空间
第一题

高斯消元
【问题描述】
everlasting觉得太无聊了，于是决定自己玩游戏！
他拿出了n个小圆，第i个的颜色是ai。接着他将这n个小圆复制m次并依次连接起来。之后他发现其中有很多颜色相同的小圆，于是他决定：每有k个连续颜色相同的小圆就将他们消去，并将剩下的依次连接。（注意只会消除k个，即使有超过k个）他将每次从头开始不断进行这个操作直到无法操作为止。他想知道最后能剩下多少个小圆？
【输入格式】
从文件guass.in中输入数据。
第一行三个正整数n,m,k,表示开始小圆的个数，复制次数和消除连续小圆的个数。
第二行n个正整数，第i个数表示第i个小圆的颜色。
【输出格式】
输出到文件guass.out中。
一个整数，表示剩余小圆的个数。
【样例输入1】
4 5 2
1 2 3 1
【样例输出1】
12
【样例说明】
原来的顺序是“1 2 3 1 1 2 3 1 1 2 3 1 1 2 3 1 1 2 3 1”共删掉8个1，剩余12个。
【样例输入2】
1 9 2
1
【样例输出2】
1
【样例说明】
剩余1个1.
【样例输入3】
3 10 2
1 2 1
【样例输出3】
0
【样例说明】
注意新形成的连续k个小圆也会消除。
【其他样例】
见下发大样例。

额，数据范围贴不上去。
这题考试的时候想出来正解了，但是写的不够优美，导致不知道错哪了。
就是找循环节，加起来就好了。
注意特判。
Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[500005];
int o;
int n,m,k;
long long p[500005][2];
int main()
{freopen("guass.in","r",stdin);freopen("guass.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}if(k==1){printf("0");return 0;}p[o][0]=-1;for(int i=1;i<=n;i++){if(a[i]==p[o][0])p[o][1]++;else {o++;p[o][1]=1;p[o][0]=a[i];}if(p[o][1]==k)o--;}n=o;long long cnt=0ll;for(int i=1;i<=n;i++){cnt+=p[i][1];}long long ans=0ll;int l=1,r=n;while(l<r&&p[l][0]==p[r][0]){if((p[l][1]+p[r][1])%k==0){l++;r--;}else {p[l][1]=(p[l][1]+p[r][1])%k;p[r][1]=0;break;}}	if(l<r){for(int i=l;i<=r;i++){ans+=p[i][1];}printf("%lld",ans*(m-1)+cnt);return 0;}else {printf("%lld",cnt+ans+p[l][1]*m%k-p[l][1]);}return 0;
}

第二题
题目描述

糖果镇
【问题描述】
yyc 来到了糖果镇，她在这里能得到好多好吃的棒棒糖^_，糖果镇的道路是一个n*m方阵，在每个点上会有一些糖果，但是yyc每到一个点都会拿走所有的糖果，并且她只能向下走或者向右走，且要从起点（1，1）走到终点（n，m），否则她会被留在糖果镇被贪婪的恶魔吃掉⊙o⊙
当然，为了不让一个人占有过多的棒棒糖，糖果镇决定让每一个人最后得到的糖果数对于p取模。所以现在yyc想请你帮她算一算这样她最多能得到多少的棒棒糖。
【输入格式】
从文件candy.in中输入数据。
第一行3个正整数n，m，p
接下来m行，每行n个数，第i行第j列a[i][j]表示该点的糖果数。
【输出格式】
输出到文件candy.out中。
一行，一个整数，表示答案。
【样例输入】
2 3 3
2 2
2 2
0 1
【样例输出】
2
【数据规模与约定】
对于前30% m<=2
对于另外20% ai和小于p
对于 100% n<=100,000 m<=3 p,a<=1,000,000,000

我们可以枚举第二次下行的分界点，然后我们可以统计出第一次下行的影响，就是第一行到x的前缀和减去第二行到x-1的前缀和，第二行就是到枚举端点的前缀和，这样在已知第二次下行的分界点时，第二行和第三行的贡献是已知的，我们只要找到模意义下第一行的最优贡献就好了，这个就可以用set维护，找前驱
Code

#include<iostream>
#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
typedef long long LL;
LL sum[4][N];
set<LL>st;
set<LL>::iterator it;int main()
{   freopen("candy.in","r",stdin);freopen("candy.out","w",stdout); int n,m;LL p;scanf("%d %d %lld", &n, &m, &p);LL mod=p, ans=0;if(m==3){for(int i=1;i<=3;i++){sum[i][0]=0;for(int j=1;j<=n;j++){LL x;scanf("%lld", &x);sum[i][j]=(sum[i][j-1]+x)%mod;}}st.clear();for(int i=1;i<=n;i++){LL x=(sum[1][i]-sum[2][i-1]+mod)%mod;st.insert(x);x=(sum[3][n]-sum[3][i-1]+sum[2][i] +mod)%mod;it=st.lower_bound(mod-x);ans=max(ans,(x+*(--it))%mod);}cout<<ans<<endl;}else{for(int i=1;i<=2;i++){sum[i][0]=0;for(int j=1;j<=n;j++){LL x;scanf("%lld", &x);sum[i][j]=(sum[i][j-1]+x)%mod;}}for (int i=1;i<=n;i++)ans=max(ans,(sum[2][n]-sum[2][i-1]+sum[1][i]+mod)%mod);cout<<ans<<endl;}return 0;
}

第三题

游戏
【问题描述】
小明和小刚正在玩如下的游戏。首先小明画一个有N个顶点，M条边的有向图。然后小刚试着摧毁它。在一次操作中他可以找到图中的一个点，并且删除它所有的入边或所有的出边。
小明给每个点定义了两个值：Wi+和Wi-。如果小刚删除了第i个点所有的入边他要给小明付Wi+元，如果他删除了所有的出边就需要给小明付Wi元。
找到小刚删除图中所有边需要的最小花费。
【输入格式】
从文件game.in中输入数据。
第一行有两个数N,M(1<=N<=100,1<=M<=5000)。
第二行有N个整数，描述了N个点的Wi+，同样的第三行是这N个点的Wi-。所有的费用都是正数并且不超过10^6。接下来的M行每行有两个数，代表有向图中相应的一条边。
【输出格式】
输出到文件game.out中。
输出一行一个整数，即小刚的最小花费。
【样例输入】
3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3
【样例输出】
5
【样例说明】
样例的一个方案是：删除点1，2所有的入边，删除点2所有的出边。
【数据规模与约定】
对于 40% 的数据满足 1<=N<=10,1<=M<=20
对于 100% 的数据满足 1<=N<=100,1<=M<=5000

沙雕网络流。。考试居然还想着费用流。。真是沙雕。。
最小割，要么割出边，要么割入边。
Code

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m;
int fst[205];
int nxt[60005];
int v[60005];
int k[60005];
int d[205];
int edge=1;
int S,T;
const int inf=1000000000;
void add(int x,int y,int val)
{edge++;nxt[edge]=fst[x];fst[x]=edge;v[edge]=y;k[edge]=val;
}
queue <int> q;
bool bfs()
{while(!q.empty())q.pop();memset(d,-1,sizeof(d));d[S]=1;q.push(S);while(!q.empty()){int x=q.front();q.pop();for(int i=fst[x];i;i=nxt[i]){if(k[i]&&d[v[i]]==-1)   {d[v[i]]=d[x]+1; q.push(v[i]);}   }}return ~d[T];
}
int dfs(int x,int val)
{if(x==T||!val)return val;int tmp=0;for(int i=fst[x];i;i=nxt[i]){if(k[i]&&d[v[i]]==d[x]+1){int flow=dfs(v[i],min(val,k[i]));val-=flow;k[i^1]+=flow;k[i]-=flow,tmp+=flow;if(!v)break;}}if(!tmp)d[x]=-1;return tmp;
}
int dinic()
{int tmp=0;while(bfs())tmp+=dfs(S,inf);return tmp;
}
int main()
{freopen("game.in", "r", stdin);freopen("game.out", "w", stdout);scanf("%d%d",&n,&m);int x;S=201;T=202;for(int i=1;i<=n;i++){scanf("%d",&x);add(T,i+n,0);add(i+n,T,x);}for(int i=1;i<=n;i++){scanf("%d",&x);add(S,i,x);add(i,S,0);}int y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);add(x,y+n,inf);add(y+n,x,0);}printf("%d",dinic());return 0;
}

我真是沙雕。