今年高一，今年省选就是去积累大赛经验的，为明年的主场做准备。考前参加过几次学校组织的模拟赛（死难死难 ），都得了不点分，所以本来就没多大目标，不爆零就行，但是也有认真复习。
闲话少叙，今年省选题总体来讲部分分还是挺好写的对于我这种蒟蒻
进考场之后发现电脑左上角没有菜单（可能是卡bug了），找不到guide了。还好我吸取之前CSP血的教训，练好了emacs，所以并无大碍。拿到题大体读了一遍，还好没考阅读理解 三道题都有点思路，就从T1开始吧。
T1我是想了一个奇怪的贪心：既然是要让极差最小，那么我们就可以把所以牌正反面的数加起来，然后求一个平均数，在把每张牌正反面的数和平均数比较，选离平均数较“近”的数在上面。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,m,sum,ans[1000005],ba,num,t;
struct node {
int z,f,yz,yf;
} a[1000005];
bool cmp(node x,node y) {
if(x.z==y.z) return x.f<y.f;
return x.z>y.z;
}
int main() {
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i].z);
sum+=a[i].z;
a[i].yz=a[i].z;
}
for(int i=1; i<=n; i++) {
scanf("%d",&a[i].f);
sum+=a[i].f;
a[i].yf=a[i].f;
}
ba=sum/(n*2)+1;
for(int i=1; i<=n; i++) {
a[i].z=abs(a[i].z-ba);
a[i].f=abs(a[i].f-ba);
}
sort(a+1,a+n+1,cmp);
for(int i=1; i<=n; i++) {
if(a[i].z>=a[i].f) {
ans[++t]=a[i].yf;
num++;
} else ans[++t]=a[i].yz;
if(num>m) break;
}
sort(ans+1,ans+t+1);
printf("%d\n",ans[t]-ans[1]);
return 0;
}
代码写出来之后复杂度并不高，并且可以过样例1，但是到了大样例就始终比答案多1，又调试了半天也没过大样例，看时间已经一个半小时了，就放下了T1去看T2了（本来这贪心就是骗分的，能骗点是点 ）
T2我写了一个暴力模拟：这题说输出任意一个即可，那应该有special judge，先把b[][]数组分解在a[][]数组里，然后以四个格为一个单位枚举，改变过了就标记不在改变。最后遍历a[][]数组，如果有大于1e6的就输出NO，没有就把a[][]数组输出。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int t,n,m,b[305][305],a[305][305],re[305][305];
bool vis[305][305];
int main() {
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d",&t);
while(t--) {
memset(vis,0,sizeof(vis));
memset(re,0,sizeof(re));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
scanf("%d%d",&n,&m);
for(int i=1; i<n; i++) {
for(int j=1; j<m; j++) {
scanf("%d",&b[i][j]);
}
}
for(int i=1; i<n; i++) {
for(int j=1; j<m; j++) {
a[i][j]+=b[i][j]/4;
a[i+1][j]+=b[i][j]/4;
a[i+1][j+1]+=b[i][j]/4;
a[i][j+1]+=b[i][j]/4+b[i][j]%4;
re[i][j]++;
re[i+1][j]++;
re[i+1][j+1]++;
re[i][j+1]++;
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
a[i][j]/=re[i][j];
}
}
for(int i=1; i<n; i++) {
for(int j=1; j<m; j++) {
int num=0;
num=a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i][j+1];
if(num==b[i][j]) {
vis[i][j]=1;
vis[i][j+1]=1;
vis[i+1][j+1]=1;
vis[i+1][j]=1;
continue;
} else {
if(vis[i][j]==0) {
a[i][j]+=b[i][j]-num;
vis[i][j]=1;
vis[i][j+1]=1;
vis[i+1][j+1]=1;
vis[i+1][j]=1;
}
if(vis[i+1][j]==0) {
a[i+1][j]+=b[i][j]-num;
vis[i][j]=1;
vis[i][j+1]=1;
vis[i+1][j+1]=1;
vis[i+1][j]=1;
}
if(vis[i][j+1]==0) {
a[i][j+1]+=b[i][j]-num;
vis[i][j]=1;
vis[i][j+1]=1;
vis[i+1][j+1]=1;
vis[i+1][j]=1;
}
if(vis[i+1][j+1]==0) {
a[i+1][j+1]+=b[i][j]-num;
vis[i][j]=1;
vis[i][j+1]=1;
vis[i+1][j+1]=1;
vis[i+1][j]=1;
}
}
}
}
int flag=0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i][j]>1000000) {
printf("NO\n");
flag=1;
}
}
}
if(flag==0) {
printf("YES\n");
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
printf("%d ",a[i][j]);
}
printf("\n");
}
}
}
return 0;
}
这个代码也能过样例，但是我这种分法显然不能使最大的点尽量小，所以有亿些有解的情况可能被我判成了无解。复杂度O(tmn)还可以接受。但我也管不了那么多了（其实是不会了 ），因为此时已经只剩一个小时了，赶紧看T3。
T3我就是纯暴力：O（mn^3）！还有谁！邻接矩阵存图！暴力删点！不解释！
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,m,e1[1005][1005],e2[1005][1005],cnt,ans,x[200005],y[200005];
int main()
{
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
e1[i][i]=e2[i][i]=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
e1[x[i]][y[i]]=e2[x[i]][y[i]]=1;
}
for(int i=1;i<=n;i++)
{
for(int p=1;p<=n;p++)
for(int q=1;q<=n;q++)
e2[p][q]=e1[p][q];
cnt=0;
for(int j=1;j<=n;j++)
{
if(e2[i][j]==1&&e2[j][i]==1)
{
cnt++;
for(int k=1;k<=n;k++)
{
e2[k][j]=0;
}
}
}
ans+=cnt;
}
printf("%d ",ans);
for(int f=1;f<=m;f++)
{
e1[x[f]][y[f]]=0;
int tot=0;
for(int i=1;i<=n;i++)
{
for(int p=1;p<=n;p++)
for(int q=1;q<=n;q++)
e2[p][q]=e1[p][q];
cnt=0;
for(int j=1;j<=n;j++)
{
if(e2[i][j]==1&&e2[j][i]==1)
{
cnt++;
for(int k=1;k<=n;k++)
{
e2[k][j]=0;
}
}
}
tot+=cnt;
}
printf("%d ",tot);
}
return 0;
}
样例也能过，大样例没时间测了。
DAY1就是这样，我觉得还算顺利，应该能拿一些分……吧？
老实说看到DAY2的题我着实有点傻眼……
题目如下：
T1宝石
T2滚榜
T3支配
前天晚上背的图论模板考了一天试已经忘得差不多了！好家伙！有点心虚！
于是先把三道题粗略读了一边，就开始研究T2：
T2一开始就有思路，先暴力全排列，然后挨个判断是否符合题意，这样复杂度虽然高，但应该能过掉不少点。当时想出这个思路之后非常兴奋，但之后就遇到了
考前全复习图论，DP什么的了，之前的全排列差不多忘光了！ 凭借记忆调了好久也不对，心态开始爆炸，眼看着一个半点过去了我还在调一个全排列的模板！心理越来越急！一个小时四十分钟的时候我先放下了T2，去看T1了
T1题面一大串，要用到dij，spfa什么的。由于调T2的心态影响，加之时间紧迫，并且我对于最短路的模板记忆也有点模糊，这要是再自己调就彻底没时间了，于是我就直奔这条特殊性质去了。
这说明这是一条直路，就好办许多，从si到ti顺着找就行了，虽然只有4个点，但是先拿上20分再说
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,m,c,p[50005],w[200005],q;
int main() {
freopen("gem.in","r",stdin);
freopen("gem.out","w",stdout);
scanf("%d%d%d",&n,&m,&c);
for(int i=1; i<=c; i++) {
scanf("%d",&p[i]);
}
for(int i=1; i<=n; i++) {
scanf("%d",&w[i]);
}
for(int i=1; i<n; i++) {
int x,y;
scanf("%d%d",&x,&y);
}
cout<<"1";
scanf("%d",&q);
while(q--) {
int u,v,ans=0;
scanf("%d%d",&u,&v);
int now=1;
for(int i=u; i<=v; i++) {
if(w[i]==p[now]) {
ans++;
now++;
}
}
printf("%d\n",ans);
}
return 0;
}
测试自己造的样例也过了，再回头看T2。（此时时间还剩一个半小时）
再看T2的时候心态缓和了不少，静下心从头开始想全排列问题，又调了一个小时，终于调出来了！
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,a[15],vis[15],ans;
void dfs(int t) {
if(t>n) {
ans++;
return;
}
for(int i=1; i<=n; i++) {
if(vis[i]==0) {
a[t]=i;
vis[i]=1;
t++;
dfs(t);
vis[i]=0;
t--;
}
}
}
int main() {
freopen("ranklist.in","r",stdin);
freopen("ranklist.out","w",stdout);
scanf("%d",&n);
a[0]=1;
dfs(1);
printf("%d",ans);
return 0;
}
然而时间只剩了20分钟，判断肯定来不及了。T3最后狗急跳墙懵了一个不那么随机的随机数……
#include<bits/stdc++.h>
using namespace std;
int n,m,q,zp1[3005][3005],zp2[3005][3005];
struct node {
int to,nxt;
} e1[6010],e2[6010];
int head[6010],cnt=0;
void add(int x,int y) {
e1[++cnt].nxt=head[x];
e2[cnt].nxt=e1[cnt].nxt;
e1[cnt].to=y;
e2[cnt].to=e1[cnt].to;
head[x]=cnt;
}
bool vis[3005],id,tot=1;
void dfs(int u,int f) {
if(u==f) {
return;
}
for(int i=head[u]; i; i=e2[i].nxt) {
int v=e2[i].to;
if(vis[v]) continue;
zp1[id][++tot]=e2[i].nxt;
vis[v]=1;
dfs(i,v);
}
}
int main() {
freopen("dominator.in","r",stdin);
freopen("dominator.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1; i<=m; i++) {
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
while(q--) {
int x,y;
scanf("%d%d",&x,&y);
cout<<rand()<<endl;
}
return 0;
}
再最后检查一下就收卷了。
首先全排列调那么长时间肯定不应该，体现出平时基础训练不够，同时对于图论模板也不够熟悉，导致开始气势上就输了。虽然DAY2应该得不了几个分，但是还是有收获，回去在加强基础，明年争取不留遗憾！
蒟蒻流泪(╥╯^╰╥)
前言 Linux下的压缩和解压缩工具比较多，有时经常记不住，这里给大家汇总一下，...
复制代码 代码如下: function keyPress(ev){ if(ev.keyCode==13){ //在光标所在...
架构图 模块职责划分 rocketmq-common通用的枚举、基类方法、或者数据结构包名有...
其实微软目前正在的做工作，就包含对Windows 10视觉效果的调整，换句话说就是，...
前言 Insert into select请慎用。这天xxx接到一个需求，需要将表A的数据迁移到表...
456...
其实出现Microsoft VBScript 编译器错误 错误 '800a03e9' 内存不够的错误一般是...
最近有个需求就是根据产品编号批量下架产品，需要下架日期为16-31号之间的产品，...
1 ansible-playbook 任务剧本 1.1 剧本文件概念 （1）playbook可以将多个批量操...
先来看一下在PHP中建立cURL请求的基本步骤： （1）初始化 curl_init() （2）设置...
