NOIP2015提高组解题
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
T1 神奇的幻方
【题目大意】告诉你幻方的构造
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
,给出N*N幻方的
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。N≤39且为奇数。【解题说明】直接模拟即可
【代码】
#include
int n,m,i,j,x,y,a[55][55];
int main(){
scanf("%d",&n);m=n*n;x=1;y=(n+1)/2;a[x][y]=1;
for(i=2;i<=m;a[x][y]=i++)
if(x==1&&y!=n)x=n,y++;else if(x!=1&&y==n)y=1,x--;
else if(x==1&&y==n)x++,a[x][y]=i;else if(!a[x-1][y+1])x--,y++;else x++;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
printf("%d",a[i][j]);
if(j
#include
#define N 222222
using namespace std;
int n,i,tm,tp,now,ans,sz,to[N],dfn[N],low[N],st[N];bool is[N];
void dfs(int x){
dfn[x]=low[x]=++tm;st[++tp]=x;is[x]=1;
int y=to[x];
if(!dfn[y])dfs(y),low[x]=min(low[x],low[y]);
else if(is[y])low[x]=min(low[x],dfn[y]);
if(low[x]==dfn[x]){
for(sz=now=0;now!=x;)now=st[tp--],sz++;
if(sz>1)ans=min(ans,sz);
}
}
int main(){
for(ans=1e9,scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&to[i]);
for(i=1;i<=n;i++)if(!dfn[i])dfs(i);
printf("%d",ans);
}
【时间复杂度】O(n) 【空间复杂度】O(n)
【思想难度】25 【编程难度】25 【总用时】15 min
T3 斗地主
【题目大意】给你一副斗地主手牌,问你最快几次出完,数据随机,牌数不超过23。【解题说明】
30分做法:N≤4,没有顺子,直接贪心即可。
60~70分做法:
①写一个非常暴力的暴力。
②写一个非常暴力的状压DP。
90分做法:状压DP再小小地优化一下,由于每种牌在读入数据出来后上限已经固定了,最差情况下是每种牌平均分布,状态
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示需要3^9*2^5=629856,转移再加一些优化,理论上能过,但CCF的机子太慢了会被卡10分
100分做法:
①还是暴力,单牌和对牌最后处理就可以了,剩下的各种情况讨论,随机数据轻松跑出。
②暴力+贪心,暴力枚顺子,剩下的牌肯定是可以贪心的,随便搞一搞就可以了
【代码】
#include
#include
#include
#define mxh 1000000007
using namespace std;
int ans,T,n,i,x,y,pai[6],cnt[15];
void find(int step){
int i,j,k,w;
if(step>=ans)return;
ans=min(ans,step+pai[1]+pai[2]+pai[3]+pai[4]);
if(pai[4])for(i=2;i<=14;i++)if(cnt[i]==4){
pai[4]--;cnt[i]-=4;
if(!pai[3]&&!pai[4]&&!pai[1]&&pai[2]<=1){
ans=min(ans,step+1);
pai[4]++;cnt[i]+=4;
return;
for(j=1;j<=14;j++)if(cnt[j]){
pai[cnt[j]]--;cnt[j]--;pai[cnt[j]]++;
for(k=j;k<=14;k++)if(cnt[k]){
pai[cnt[k]]--;cnt[k]--;pai[cnt[k]]++;
find(step+1);
pai[cnt[k]]--;cnt[k]++;pai[cnt[k]]++;
}
pai[cnt[j]]--;cnt[j]++;pai[cnt[j]]++;
}
if(pai[2]||pai[3]||pai[4])for(j=2;j<=14;j++)if(cnt[j]>1){
pai[cnt[j]]--;cnt[j]-=2;pai[cnt[j]]++;
for(k=j;k<=14;k++)if(cnt[k]>1){
pai[cnt[k]]--;cnt[k]-=2;pai[cnt[k]]++;
find(step+1);
pai[cnt[k]]--;cnt[k]+=2;pai[cnt[k]]++;
}
pai[cnt[j]]--;cnt[j]+=2;pai[cnt[j]]++;
}
pai[4]++;cnt[i]+=4;
}
if(pai[3])for(i=2;i<=14;i++)if(cnt[i]>=3){
pai[cnt[i]]--;cnt[i]-=3;pai[cnt[i]]++;
find(step+1);
for(j=1;j<=14;j++)if(cnt[j]){
pai[cnt[j]]--;cnt[j]--;pai[cnt[j]]++;
find(step+1);
pai[cnt[j]]--;cnt[j]++;pai[cnt[j]]++;
}
if(pai[2]||pai[3]||pai[4])for(j=2;j<=14;j++)if(cnt[j]>1){
pai[cnt[j]]--;cnt[j]-=2;pai[cnt[j]]++;
find(step+1);
pai[cnt[j]]--;cnt[j]+=2;pai[cnt[j]]++;
}
pai[cnt[i]]--;cnt[i]+=3;pai[cnt[i]]++;
}
if(pai[3]+pai[4]>=2)for(i=3;i<14;i++)if(cnt[i]>=3&&cnt[i+1]>=3){ pai[cnt[i]]--;cnt[i]-=3;pai[cnt[i]]++;w=i;
for(j=i+1;cnt[j]>=3&&j<=14;j++){
pai[cnt[j]]--;cnt[j]-=3;pai[cnt[j]]++;
find(step+1);w=j;
}
for(j=i;j<=w;j++){
pai[cnt[j]]--;cnt[j]+=3;pai[cnt[j]]++;
}
if(pai[2]+pai[3]+pai[4]>=3)for(i=3;i<13;i++)if(cnt[i]>=2&&cnt[i+1]>=2&&cnt[i+2]>=2){ pai[cnt[i]]--;cnt[i]-=2;pai[cnt[i]]++;
pai[cnt[i+1]]--;cnt[i+1]-=2;pai[cnt[i+1]]++;w=i+1;
for(j=i+2;cnt[j]>=2&&j<=14;j++){
pai[cnt[j]]--;cnt[j]-=2;pai[cnt[j]]++;
find(step+1);w=j;
}
for(j=i;j<=w;j++){
pai[cnt[j]]--;cnt[j]+=2;pai[cnt[j]]++;
}
}
if(pai[1]+pai[2]+pai[3]+pai[4]>=5)for(i=3;i<11;i++)if(cnt[i]&&cnt[i+1]&&cnt[i+2]&&cnt[i +3]&&cnt[i+4]){
pai[cnt[i]]--;cnt[i]--;pai[cnt[i]]++;
pai[cnt[i+1]]--;cnt[i+1]--;pai[cnt[i+1]]++;
pai[cnt[i+2]]--;cnt[i+2]--;pai[cnt[i+2]]++;
pai[cnt[i+3]]--;cnt[i+3]--;pai[cnt[i+3]]++;w=i+3;
for(j=i+4;cnt[j]&&j<=14;j++){
pai[cnt[j]]--;cnt[j]--;pai[cnt[j]]++;
find(step+1);w=j;
}
for(j=i;j<=w;j++){
pai[cnt[j]]--;cnt[j]++;pai[cnt[j]]++;
}
}
}
int main(){
for(scanf("%d%d",&T,&n);T--;){
ans=12;
memset(cnt,0,sizeof(cnt));
memset(pai,0,sizeof(pai));
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
if(x==1)x=14;
if(x==0)x=1;
cnt[x]++;
}
for(i=1;i<=14;i++)pai[cnt[i]]++;
find(0);
printf("%d\n",ans);
}
}
【时间复杂度】O(?) 【空间复杂度】O(?)
【思想难度】27 【编程难度】51 【总用时】45 min
T4 跳石头
【题目大意】给你一排N块石头,你可以移走M块石头,使得最小的两块石头之间的距离尽可能长,N,M≤50000。
【解题说明】
20分做法:直接暴力即可
50分做法:考虑DP,f[i][j]表示在前i块石头移走j块石头的最短距离,转移即可
60分做法:考虑贪心,每次删除间距最小的,用堆维护
100分做法:考虑二分
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
后贪心,先二分这个距离使其变为判断可行性问题,然后从前往后扫,一旦这个石头到上一个选的石头的距离小于这个二分的答案就把这块石头移走
这样显然是正确的,很容易证明先移一定比后移好,所以这个算法是正确的
【代码】
#include
int L,n,m,i,w,l,r,mid,pos,ans,a[55555];
bool ok(int x){
for(pos=w=0,i=1;i<=n;i++)if(a[i]-pos>1))ans=mid,l=mid+1;else r=mid-1;
printf("%d",ans);
}
【时间复杂度】O(nlgL) 【空间复杂度】O(n)
【思想难度】30 【编程难度】23 【总用时】10 min
T5 子串
【题目大意】有两个字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串,然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串,问有多少种方案可以使得这个新串与字符串B相等?A的长度≤1000,B的长度≤200,k≤200。
【解题说明】
特殊的10分做法:k=1,所以直接扫一遍判断就可以了
特殊的20分做法:k=2,所以枚举分隔点再扫一遍判断就可以了
特殊的20分做法:k=m,所以从前往后扫一遍DP统计一下方案就可以了
70分做法:考虑dp,用f[i][j][k]表示A串匹配到第i个字符,B串匹配到第j个字符,已经取了k个互不重叠的非空子串的方案数,那么f[i][j][k]=Σf[i-w-o][j-w][k-1](w=1-A[i]和B[j]的最大后缀匹配,i-w-o>=0),f[0][0][0]=1,这样直接转移的复杂度是O(nm^3k)的,把o这一维前缀和转移一下,就是O(nm^2k)的,可以通过70分的数据。
90分做法:再把w也前缀和转移掉,就可以通过90分的数据。
100分做法:加一个滚动数组,然后再卡一卡常,就可以通过100分的数据。
【代码】(90)
继续阅读
浙公网安备 33021202002483