构造

题目链接 题意： # 给f[1],f[2],n,f[i] = 2*f[i-2] + f[i-1] + i^4，求f[n]的值。

题目链接 题意： # 求f[n] = f[n-1] + f[n-2] + 1，在b(10000)进制下的最后一位数字的十进制表示。

hdu4686题目链接 题意： # An Arc of Dream is a curve defined by following function:

题目链接 题意： # 给出了一段程序，程序实际算的是f[n] = (f[n-1] + n%2)%m的值，其中f[1]=1，给出n,m(1E9)，问f[n]

给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。

题目链接 题意： m个区间，要求构造一个长度为n的数组，满足m个区间中，每个区间的mex值中的最小值最大。

题目链接 题意：给一个n*m的由小写字母组成的table.要求从上往下每一行字典序不严格递增。问最少删除几列才能满足。

题目链接 题意：n堆石子，每堆a[i]个，k种颜色。给每个石子涂色，要求对于每种颜色，任意两堆中该颜色石子的个数最多差一个。问是否有解，有解输出一组方案。

题目链接 题意：给出n，有1..n n个数，可以选择两个数进行加，减，乘，三种操作，操做完得到一个数放回。 n-1次操作后只剩下一个数。现在要求剩下的数为24.问方法。

题目链接 题意：存在一个[2..100]之间的数，每次可以询问一个数是否是该数的因子，返回yes或者no，最多询问20次。每次要输出询问的数，以及最后要输出这个数是否是质数。

题目链接：题目链接 题意：给出一个无向图，该图是通过仅包含‘a’ ‘b’ ‘c’三个字母，以规则“i,j之间有边，当且仅当s[i]和s[j]相同，或者s[i]和s[j]在字母表中相邻”（也就是只有’a’和’c’是没有边相连的）得到的，现在问能否还原这个字符串，如果能，输出任意一个解。

题目链接 题意：给出一个数，问包含这个数三个数组成的勾股数，输出另外两个数。

题目链接 题意：给出n个元素的序列，问能否得到一个新的序列，使得奇数位置非递减排列，偶数位数非递增排列。 思路：感觉一定可以啊。。。排序以后直接构造。。。

http://codeforces.com/contest/625/problem/D 题意：问能否找到一个s，满足s+s的反转=k 思路：如果是回文数。。。那么显然满足。除以2就可以得到答案。 代码实现 1 如果不是回文数。。那么考虑进位的情况。 2 要么从后一位进1，要么从前一位退10回来。 3 需要特殊考虑1开头的。 4 5 6 7/* *********************************************** 8Author :111qqz 9Created Time :2016年02月07日 星期日 18时28分39秒 10File Name :code/cf/#342/D.cpp 11************************************************ */ 12 13#include <cstdio> 14#include <cstring> 15#include <iostream> 16#include <algorithm> 17#include <vector> 18#include <queue> 19#include <set> 20#include <map> 21#include <string> 22#include <cmath> 23#include <cstdlib> 24#include <ctime> 25#include <sstream> 26#define fst first 27#define sec second 28#define lson l,m,rt<<1 29#define rson m+1,r,rt<<1|1 30#define ms(a,x) memset(a,x,sizeof(a)) 31typedef long long LL; 32#define pi pair < int ,int > 33#define MP make_pair 34 35using namespace std; 36const double eps = 1E-8; 37const int dx4[4]={1,0,0,-1}; 38const int dy4[4]={0,-1,1,0}; 39const int inf = 0x3f3f3f3f; 40const int N=1E5+7; 41bool vis[N]; 42 43void pre() 44{ 45 ms(vis,false); 46 for ( int i = 10 ; i <12000 ; i++) 47 { 48 int vala = i ; 49 stringstream ss; 50 ss<<vala; 51 string tmp = ss.str(); 52 53 reverse(tmp.begin(),tmp.end()); 54 55 int valb; 56 sscanf(tmp.c_str(),"%d",&valb); 57// cout<<i<<" "<<vala+valb<<endl; 58 if (vala+valb<N) vis[vala+valb] = true; 59 60 } 61 62 for ( int i = 1 ; i < N ; i++) 63 { 64 if (vis[i]) cout<<i<<endl; 65 } 66} 67char ans[N],s[N]; 68int n; 69int sum[N]; 70 71bool ok() 72{ 73 // cout<<"n:"<<n<<endl; 74 for ( int i = 0 ; i < n/2 ;) 75 { 76 int l = i ; 77 int r = n-1-i; 78 if (sum[l]==sum[r]) i++; 79 else if (sum[l]==sum[r]+1||sum[l]==sum[r]+11) 80 { 81 sum[l]--; 82 sum[l+1]+=10; 83 } 84 else if (sum[l]==sum[r]+10) 85 { 86 sum[r-1]--; 87 sum[r]+=10; 88 89 } 90 else return false; 91 } 92 93 if (n%2==1) 94 { 95 if (sum[n/2]%2==1) return false; 96 if (sum[n/2]>18||sum[n/2]<0) return false; 97 ans[n/2] = char(sum[n/2]/2 +'0'); 98// cout<<"ASDHJKASD"<<endl; 99 } 100 for ( int i = 0 ; i < n/2 ; i++) 101 { 102 if (sum[i]<0||sum[i]>18) return false; 103 ans[i] =(sum[i]+1)/2+'0'; 104 ans[n-1-i] =sum[i]/2+'0'; 105 } 106 return ans[0]>'0'; 107} 108int main() 109{ 110 #ifndef ONLINE_JUDGE 111 freopen("code/in.txt","r",stdin); 112 #endif 113 114 //pre(); 115 // 116 117 scanf("%s",s); 118 n = strlen(s); 119 for ( int i = 0 ; i < n ; i++) sum[i] = s[i] - '0'; 120 if (ok()) 121 { 122 cout<<ans<<endl; 123// cout<<"aaa"<<endl; 124 return 0; 125 } 126 127 if (s[0]=='1'&&n>1) 128 { 129 for ( int i = 0 ; i < n ; i++) 130 sum[i] = s[i+1]-'0'; 131 sum[0]+=10; 132 n--; 133 if (ok()) 134 { 135 cout<<ans<<endl; 136 return 0; 137 } 138 else 139 puts("0"); 140 } 141 else puts("0"); 142 143 144 #ifndef ONLINE_JUDGE 145 fclose(stdin); 146 #endif 147 return 0; 148}

http://codeforces.com/contest/625/problem/C 题意：构造一个矩阵。。满足三个条件。。。 思路：简单构造。。。看代码把。。。。

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1726 题意：给出26个大写字母的权值，要求构造一个长度为n（n不超过210）的字符串。并且满足奇数位置只能放元音字母，偶数位置只能放辅音字母，且每个元音字母最多放21次，每个辅音字母最多放5次，要求构造的字符串的权值之和最小，在权值最小的前提下字典序最小。

http://codeforces.com/contest/22/problem/C 题意：要求用n个点m条边构造一个不允许有重边的图，满足当去掉点v的时候，剩下的n-1个不联通。如果有答案输出任意，没答案输出-1. 思路：首先如果n个点要联通。。至少有n-1条边，此时为一棵树。但是是不是边越多越好呢？显然是不可以的。满足去掉一个点使得n-1个点不联通的情况为，存在一个点u只和v相连，不和任意任何其他点相连，那么当去掉v点，u点就变成不可到达了。边数最多的情况就是，除了v点以外的n-1个点，每个点的度都是n-2(去掉自身以及u点还有n-2个点)，，那么除去u点以外的n-1个点的度数就是（n-1）(n-2)，边数则为(n-1)(n-2)/2，再加一条连接u的边，所以图的最大边数为(n-1)*(n-2)/2+1，最小为n-1.

http://codeforces.com/problemset/problem/600/C 题意：给定一个字符串。要求用最少的变换得到一个回文串。且在变换次数相同时要字典序最小的。输出变换后的字符串。 思路：对不能构成会文串有影响的是出现奇数次的字母。所以我们先统计每个字母出现的次数。然后按照出现奇数次的字母的个数分奇偶分别搞。偶数的话直接把后面一半变成前面一半。奇数的话，也是这样。输出的时候按照字母从a扫到z，如果有就输出一半。然后再倒着扫一遍。 输出另一半。这样可以保证是字典序最小。需要注意的是奇数的时候的输出情况。不要忘记中间那个字母。

http://codeforces.com/contest/377/problem/A 题意：给定一个n*m的maze. ‘.’代表空，‘#’代表墙。要求构造一种方案，使得将k个空格填成墙壁后不影响当前的连通性（即没有被填充的空格之间可以相互到达） 思路：一开始想从上往下从左往右构造。错误的认为四个角一定是可以变成墙的。

c语言上机。。。。 c写的幻方。 代码实现 1/************************************************************************* 2> File Name: code/class/7.c 3> Author: 111qqz 4> Email: rkz2013@126.com 5> Created Time: 2015年11月11日 星期三 19时31分50秒 6************************************************************************/ 7 8#include<stdio.h> 9#include <string.h> 10 11int n; 12int a[105][105]; 13 13 14 15void swap(int *a,int *b) 16{ 17int tmp; 18tmp = *a; 19*a = *b; 20*b = tmp; 21} 22int fix_x( int x,int k,int n) 23{ 24if (k%2==1) 25{ 26if (x==0) 27return n; 28else return x; 29} 30else 31{ 32if (x==n) 33return n+n; 34else return x; 35} 36} 37int fix_y ( int y,int k,int n) 38{ 39if (k<3) 40{ 41if (y==n+1) 42return 1; 43else return y; 44} 45else 46{ 47if (y==2*n+1) 48return n+1; 49else return y; 50} 51// if (y==n+1) 52// return 1; 53// else return y; 54} 55void print() 56{ 57for ( int i = 1 ; i <= n ; i++) 58{ 59for ( int j = 1 ; j <= n ; j++) 60printf("%d ",a[i][j]); 61 61 62printf("n"); 63} 64 64 65} 66 66 67void OddMagic(int n,int x,int y,int k) //k表示4中状态。。。。 68{ 69 69 70int cur ; 71if (k==1) cur = 1; 72if (k==4) cur = n*n+1; 73if (k==3) cur = n*n*2+1; 74if (k==2) cur = n*n*3+1; 75int cnt = 1; 76while (cnt<=n*n) 77{ 78a[x][y]=cur; 79int prex = x; 80int prey = y; 81cur++; 82cnt++; 83x--; 84y++; 85x = fix_x(x,k,n); 86y = fix_y(y,k,n); 87if (a[x][y]) 88{ 89x = prex+1; 90y = prey; 91} 92 92 93} 94 94 95} 96int main() 97{ 98memset(a,sizeof(a),0); 99scanf("%d",&n); 100if (n%2==1) 101{ 102int x = 1; 103int y = n/2+1; 104OddMagic(n,x,y,1); 105} 106else 107{ 108if (n%4==0) 109{ 110for ( int i = 1,num=1 ; i <= n ; i++) 111for ( int j = 1 ; j <= n ; j++,num++) 112a[i][j]=num; 113 114 115for ( int i = 1 ; i <= n ; i++) 116{ 117for ( int j = 1 ; j <= n ; j++) 118{ 119if (i==j||i+j>=n+1) continue; 120int tmp; 121tmp = a[i][j]; 122a[i][j] = a[n+1-i][n+1-j]; 123a[n+1-i][n+1-j] = tmp; 124} 125} 126} 127else 128{ 129int x = 1; 130int y = n/4+1; 131int hn = n/2; 132 133OddMagic(hn,x,y,1); 134OddMagic(hn,x+hn,y,2); 135OddMagic(hn,x,y+hn,3); 136OddMagic(hn,x+hn,y+hn,4); 137 138int m = n/4; 139for ( int i = 1 ; i <= hn ;i++) 140{ 141for ( int j = 1 ; j <= m ; j++) 142{ 143int tmp; 144if (i==m+1&&j==m) 145{ 146tmp = a[m+1][m+1]; 147a[m+1][m+1] = a[m+1+hn][m+1]; 148a[m+1+hn][m+1] = tmp; 149continue; 150 151} 152tmp = a[i][j]; 153a[i][j] = a[i+hn][j]; 154a[i+hn][j] = tmp; 155// swap(a[i][j],a[i+n][j]); 156} 157} 158 159for ( int i = 1 ; i <= hn ; i++) 160{ 161for ( int j = n ; j>=n-m+2 ; j--) 162{ 163int tmp; 164tmp = a[i][j]; 165a[i][j] = a[i+hn][j]; 166a[i+hn][j] = tmp; 167} 168} 169 170 171 172 173} 174} 175print(); 176 177}