大連大學兩日游———2021省選聯考游記
今年高一，今年省選就是去積累大賽經驗的，為明年的主場做準備，考前參加過幾次學校組織的模擬賽（死難死難 ），都得了不點分，所以本來就沒多大目標，不爆零就行，但是也有認真復習，
閑話少敘，今年省選題總體來講部分分還是挺好寫的對于我這種蒟蒻
DAY1：
題目如下：
T1卡牌游戲
T2矩陣游戲
T3圖函式
進考場之后發現電腦左上角沒有選單（可能是卡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：
老實說看到DAY2的題我著實有點傻眼……
題目如下：
T1寶石
T2滾榜
T3支配
DAY1都考了一個圖論了DAY2又來兩個？！
前天晚上背的圖論模板考了一天試已經忘得差不多了！好家伙！有點心虛！
于是先把三道題粗略讀了一邊，就開始研究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總體來說還是有點拉胯的
首先全排列調那么長時間肯定不應該，體現出平時基礎訓練不夠，同時對于圖論模板也不夠熟悉，導致開始氣勢上就輸了，雖然DAY2應該得不了幾個分，但是還是有識訓，回去在加強基礎，明年爭取不留遺憾！
最后：這篇博客就是對省選經歷的一次記錄，里面代碼可能根本就是錯的，還望不小心刷到這篇博客的大佬們勿噴
蒟蒻流淚(╥╯^╰╥)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275080.html
標籤：其他
上一篇：2021年春季ACM訓練賽第5場
下一篇：【C語言學習筆記——3】