NOIp2018集训test-9-1(pm)

欢乐%你赛，大家都AK了。

1. 小澳的方阵

吸取了前几天的教训，我一往复杂的什么二维树状数组上想就立刻打住阻止自己，就可以发现它是超级大水题了。记录每一行每一列最后一次的修改，对每个格子看它所在行和列哪一个修改更靠后即可。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,m,q,h[N][],l[N][];

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("matrix.in","r",stdin);

     freopen("matrix.out","w",stdout);

 #endif

     read(n); read(m); read(q);

     For(i,,q) {

         int x,y,z;

         read(x); read(y); read(z);

         if(x==) h[y][]=z,h[y][]=i;

         else l[y][]=z,l[y][]=i;

     }

     For(i,,n) {

         For(j,,m) {

             if(h[i][]<l[j][]) printf("%d ",l[j][]);

             else printf("%d ",h[i][]);

         } puts("");

     }

     Formylove;

 }

2. 小澳的坐标系

可以暴搜或者打个n^2dp(根据竖着走上多少行，每一行走多少步，往左还是往右dp)找规律。我不会找规律，就继续yy怎么更优秀地dp。

f[i][0]表示走i步的方案，f[i][1]表示走i步且最后一步往上走的方案。

若最后一步往左走，下一步可以往左，往上 2种走法

若最后一步往右走，下一步可以往右，往上 2种走法

若最后一步往上走，下一步可以往左，往右，往上 3种走法

所以 f[i][0]=f[i-1][0]*2+f[i-1][1]

显然 f[i][1]=f[i-1][0]

这个递推方程一出来，就可以套矩乘板子了。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=,p=1e9+;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n;

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 struct jz {

     LL a[][];

     friend jz operator *(const jz&A,const jz&B) {

         jz rs;

         For(i,,) For(j,,) {

             rs.a[i][j]=;

             For(k,,)

                 (rs.a[i][j]+=A.a[i][k]*B.a[k][j]%p)%=p;

         }

         return rs;

     }

 }bs,rs;

 void ksm(int b) {

     while(b) {

         if(b&) rs=rs*bs;

         bs=bs*bs;

         b>>=;

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("coordinate.in","r",stdin);

     freopen("coordinate.out","w",stdout);

 #endif

     read(n);

     rs.a[][]=rs.a[][]=;

     rs.a[][]=rs.a[][]=;

     bs.a[][]=; bs.a[][]=;

     bs.a[][]=; bs.a[][]=;

     ksm(n-);

     LL ans=(3LL*rs.a[][]%p+1LL*rs.a[][])%p;

     printf("%lld\n",ans);

     Formylove;

 }

3．小澳的葫芦

dp[x][y]表示从1到x经过y个点的最短路。

DAG上dp,拓扑排序即可。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=,M=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,m,f[N][N];

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 int ecnt,fir[N],nxt[M],to[M],val[M],in[N];

 void add(int u,int v,int w) {

     nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w; in[v]++;

 }

 queue<int>que;

 void tpsort() {

     memset(f,/,sizeof(f));

     int inf=f[][];

     f[][]=;

     For(i,,n) if(!in[i]) que.push(i);

     while(!que.empty()) {

         int x=que.front();

         que.pop();

         for(int i=fir[x];i;i=nxt[i]) {

             in[to[i]]--;

             if(!in[to[i]]) que.push(to[i]);

             For(j,,n) if(f[x][j]!=inf) {

                 if(f[x][j]+val[i]<f[to[i]][j+])

                     f[to[i]][j+]=f[x][j]+val[i];

             }

         }

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("calabash.in","r",stdin);

     freopen("calabash.out","w",stdout);

 #endif

     read(n); read(m);

     For(i,,m) {

         int u,v,w;

         read(u); read(v); read(w);

         add(u,v,w);

     }

     tpsort();

     db ans=1e18;

     For(i,,n) ans=min(ans,(db)f[n][i]/(1.0*i));

     printf("%lf\n",ans);

     Formylove;

 }

巴特西

NOIp2018集训test-9-1(pm)

最新文章

热门文章