一些简单题(1)（Source : NOIP历年试题+杂题）

最近也写了些许题目吧，还是写写博客，捋捋思路。

P2216 [HAOI2007]理想的正方形

求一个$a imes b(a,b leq 10^3)$的矩阵，求出一个$n imes n (n leq 100)$的矩阵，设矩阵中元素最小值$Min$,最大值$Max$，

最小化$Max - Min$

Sol : 这个题事实上只需要暴力扫每个子矩阵即可。复杂度是$O(abn)$

预处理对点$(i,j)$的$ Max[i][j] = maxlimits_{k=i-n+1}^{i} a[k][j]$

枚举每个子矩阵的时候，求$(i,j)$为左下角的$n imes n$子矩阵的

$MAX=maxlimits_{k=j-n+1}^{j} Max[i][k]$而$MIN$的处理同理。

// luogu-judger-enable-o2
# include<bits/stdc++.h>
# define int long long
using namespace std;
const int N=1e3+10;
int w[N][N];
int Max[N][N],Min[N][N];
int a,b,n,ans=0x3f3f3f3f;
signed main()
{
    scanf("%lld%lld%lld",&a,&b,&n);
    for (int i=1;i<=a;i++)
     for (int j=1;j<=b;j++)
      scanf("%lld",&w[i][j]);
    memset(Max,-0x3f,sizeof(Max));
    memset(Min,0x3f,sizeof(Min));
    for (int i=1;i<=a;i++)
     for (int j=1;j<=b;j++) {
         if (j<n) continue;
         for (int k=j;k>=j-n+1;k--)
          Min[i][j]=min(Min[i][j],w[i][k]),
          Max[i][j]=max(Max[i][j],w[i][k]);
     }
    for (int i=1;i<=a;i++)
     for (int j=1;j<=b;j++) {
         int mi=0x3f3f3f3f,ma=-0x3f3f3f3f;
         if (i<n) continue;
         for (int k=i;k>=i-n+1;k--) 
          mi=min(mi,Min[k][j]),ma=max(ma,Max[k][j]);
         if (ma-mi<ans&&ma-mi>=0) ans=ma-mi;
    }  
    printf("%lld
",ans);
    return 0;
 }

P2216.cpp

dfs(a,b,c)表示当前选择第$a$只猪，前确定了$b$条解析式，前面$c$只猪是单着被打中的（还没有确定一条解析式）

A. 单独使用一只鸟击中。 B. 被之前确定的一条解析式打中。 C. 和之前某一只猪构成抛物线（三点构成一条抛物线）

# include <bits/stdc++.h> using namespace std; const int N=20; const double eps=1e-8; struct rec{ double x,y; }w[N]; int n,ans; vector<int>single; vector<pair<double,double> >pwx; void dfs(int a,int b,int c) { if (b+c>=ans) return; if (a>n) { ans=min(ans,b+c); return;} single.push_back(a); dfs(a+1,b,c+1); single.pop_back(); bool ff=false; for (int i=0;i<pwx.size();++i) { double pa=pwx[i].first,pb=pwx[i].second; if (fabs(pa*w[a].x*w[a].x+pb*w[a].x-w[a].y)<=eps) { dfs(a+1,b,c); ff=true; break; } } if (ff) return; for (int i=0;i<single.size();++i) { int id=single[i]; if (fabs(w[a].x-w[id].x)<=eps) continue; double pa=(w[a].y*w[id].x-w[id].y*w[a].x)/(w[a].x*w[id].x*(w[a].x-w[id].x)); double pb=(w[a].y-pa*w[a].x*w[a].x)/w[a].x; if (pa>=0.0) continue; single.erase(single.begin()+i); pwx.push_back(make_pair(pa,pb)); dfs(a+1,b+1,c-1); single.insert(single.begin()+i,id); pwx.pop_back(); } } int main() { int T; scanf("%d",&T); while (T--) { ans=0x3f3f3f3f; single.clear(); pwx.clear(); int t; scanf("%d%d",&n,&t); for (int i=1;i<=n;i++) scanf("%lf%lf",&w[i].x,&w[i].y); dfs(1,0,0); printf("%d ",ans); } return 0; }

# include <bits/stdc++.h> # define int long long using namespace std; const int N=1e7+7; int pr[N]; bool is_pr[N]; void EouLaSha(int Lim) { memset(is_pr,true,sizeof(is_pr)); is_pr[1]=false; for (int i=2;i<=Lim;i++) { if (is_pr[i]) pr[++pr[0]]=i; for (int j=1;j<=pr[0]&&i*pr[j]<=Lim;j++) { is_pr[i*pr[j]]=false; if (i%pr[j]==0) break; } } } signed main() { EouLaSha(1e7); int n; scanf("%lld",&n); int ret=1; for (int i=1;i<=pr[0];i++) if (n%pr[i]==0) { int times=0; while (n>1&&n%pr[i]==0) times++,n/=pr[i]; ret=ret*(2*times+1); } if (n>1) ret=ret*(2+1); printf("%lld ",(ret+1)>>1); return 0; }

// luogu-judger-enable-o2 # include<bits/stdc++.h> # define int long long using namespace std; const int N=1e5+10; bool mark[N]; int d[N][25],b[N],g[N][25],help[N],tmp[N]; int size[N],n,m; vector<int>rec[N]; struct rec{ int pre,to,w; }a[N<<1]; int head[N],tot; void dfs1(int u,int fa) { size[u]=1; g[u][0]=fa; for (int i=head[u];i;i=a[i].pre) { int v=a[i].to; if (v==fa) continue; d[v][0]=a[i].w; dfs1(v,u); size[u]+=size[v]; } } void init() { dfs1(1,0); for (int i=1;i<=21;i++) for (int j=1;j<=n;j++) g[j][i]=g[g[j][i-1]][i-1], d[j][i]=d[j][i-1]+d[g[j][i-1]][i-1]; } void adde(int u,int v,int w) { a[++tot].pre=head[u]; a[tot].to=v; a[tot].w=w; head[u]=tot; } bool dfs2(int u,int fa) { if (mark[u]) return true; if (size[u]==1) { if (mark[u]) return true; else return false; } bool flag=true; for (int i=head[u];i;i=a[i].pre) { int v=a[i].to; if (v==fa||mark[v]) continue; flag&=dfs2(v,u); } return flag; } bool check(int Mid) { memset(mark,false,sizeof(mark)); for (int i=1;i<=n;i++) rec[i].clear(); for (int i=1;i<=m;i++) { int dist=0,u=b[i]; for (int j=21;j>=0;j--) if (g[u][j]>1&&dist+d[u][j]<=Mid) { dist+=d[u][j]; u=g[u][j]; } if (g[u][0]==1) { dist+=d[u][0]; if (dist>Mid) mark[u]=true; else { rec[u].push_back(Mid-dist); } } else mark[u]=true; } for (int i=1;i<=n;i++) sort(rec[i].begin(),rec[i].end()); help[0]=0; for (int i=head[1];i;i=a[i].pre) { int v=a[i].to; if (dfs2(v,1)) continue; bool flag=true; for (int j=0;j<rec[v].size();j++) if (rec[v][j]<a[i].w) { rec[v].erase(rec[v].begin()+j);flag=false;break;} if (!flag) continue; help[++help[0]]=a[i].w; } tmp[0]=0; for (int i=head[1];i;i=a[i].pre) { int v=a[i].to; for (int j=0;j<rec[v].size();j++) tmp[++tmp[0]]=rec[v][j]; } sort(tmp+1,tmp+1+tmp[0]); sort(help+1,help+1+help[0]); if (help[0]==0) return true; int pt1=1,pt2=1; while (pt1<=tmp[0]) { if (pt2>help[0]) return true; while (tmp[pt1]>=help[pt2]&&pt2<=help[0]&&pt1<=tmp[0]) pt1++,pt2++; if (pt2>help[0]) return true; pt1++; } return false; } signed main() { scanf("%lld",&n); int l=0,r=0,ans=-1; for (int i=1;i<n;i++) { int u,v,w; scanf("%lld%lld%lld",&u,&v,&w); r+=w; adde(u,v,w); adde(v,u,w); } scanf("%lld",&m); for (int i=1;i<=m;i++) scanf("%lld",&b[i]); init(); while (l<=r) { int mid=(l+r)>>1; if (check(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%lld ",ans); return 0; }

一些简单题(1)（Source : NOIP历年试题+杂题）

相关推荐