解析

本題也算看了一半題解吧
看到“數(shù)學歸納法”退出來自己推的
這題想到歸納法后面也就簡單了

首先，n=3和n=4的時候顯然有解，可以打表
然后考慮在獲得n-2的答案時，如何獲得n的答案
如果n為奇數(shù)，我們可以把(1,n-1,2,n)、(3,n-1,4,n)…(n-4,n-1,n-3,n)各連兩次，最后連兩個(n-2,n-1,n)
如果n為偶數(shù)，我們可以把(1,n-1,2,n)、(3,n-1,4,n)…(n-5,n-1,n-4,n)各連兩次，最后連一個(n-3,n-1,n-2,n)、(n-3,n-1,n)和(n-2,n-1,n)
然后…這道黑題就解決了…
（本人自己寫了個checker，歡迎取用）

代碼

#include<bits/stdc++.h> const int N=2e6+100; const int mod=1e9+7; #define ll long long using namespace std; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m; int num[N],x[N],y[N],z[N],k[N],tot; inline void add(int a,int b,int c){++tot;x[tot]=a;y[tot]=b;z[tot]=c;num[tot]=3; } inline void add(int a,int b,int c,int d){++tot;x[tot]=a;y[tot]=b;z[tot]=c;k[tot]=d;num[tot]=4; } void work(int n){if(n==1) return;if(n==4){add(1,2,3);add(2,3,4);add(3,4,1);add(4,1,2);return;}if(n&1){for(int i=1;i<=n-3;i+=2) add(i,n-1,i+1,n),add(i,n-1,i+1,n);add(n-2,n-1,n);add(n-2,n-1,n);work(n-2);}else{for(int i=1;i<=n-4;i+=2) add(i,n-1,i+1,n),add(i,n-1,i+1,n);add(n-3,n-1,n);add(n-2,n-1,n);add(n-3,n-1,n-2,n);work(n-2);} } int main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();work(n);//printf("%d ",n);printf("%d\n",tot);for(int i=1;i<=tot;i++){printf("%d ",num[i]);if(num[i]==3) printf("%d %d %d\n",x[i],y[i],z[i]);else printf("%d %d %d %d\n",x[i],y[i],z[i],k[i]);} } /* 1 281239 */

checker

#include <cstdio>//checker by wind_whisper #include <algorithm>using namespace std; #define ll long long const int N = 1e6 + 10; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,m; int vis[900][900],x[5]; int main() {freopen("a.out","r",stdin);n=read();m=read();for(int i=1;i<=m;i++){int k=read();for(int j=1;j<=k;j++){x[j]=read();if(j>1) vis[x[j]][x[j-1]]++,vis[x[j-1]][x[j]]++;}vis[x[1]][x[k]]++;vis[x[k]][x[1]]++;}for(int i=1;i<=n;i++){for(int j=1;j<i;j++){if(vis[i][j]!=2){printf("WA! (%d %d) have %d edges\n",i,j,vis[i][j]);return 0;}}}printf("AC!\n");return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF819E:Mister B and Flight to the Moon（构造、归纳法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。