得分情况：

　　　估分：

　　　　30(T1)+100(T2)+0(T3)=130;

　　　实际：

　　　　30(T1)+60(T2)+10(T3)=100; QAQ

　　　　　是我高看自己了

T1 友好数对：

　　题意：

　　　　　如果一个数a能由一个数b旋转得到，那么我们称为友好数对，如12345和45123为友好数对，12345和54321不为友好数对。给出两个正整数L，R，求有多少友好数对,满足L<=a (说实话没看懂后面这什么玩意)

　　　　　输入格式：

　　　　　　　第一行一个整数T，表示数据组数，每组数据两个正整数L,R。

　　　　　输出格式：

　　　　　　　对于每组数据，输出一个整数表示答案。　

　　　　　样例输入：

　　　　　样例输出：

　　　　　数据范围：

　　　　　　　对于30%的数据满足L,R<=1000
　　　　　　　对于100%的数据满足L,R<=2000000，T<=30,L,R位数相同。

　　　大概理解为：一个数a 把a分为两段两段长度不能为零然后把这两段交换位置得到b 要求L<=a,b<=R且a!=b 然后求有多少对这样的数

　　　列如： a=12345，把a分成123、45两段，然后交换得45、123 ，粘起来就成了b=45123；

　　分析：

　　　　　　看一下数据范围 L,R<=2*1e6,T<=30；

　　　　　　大概算一下2*1e6*30=6*1e7 暴力枚举完全搞得定

　　　　　　因为一个数可能旋转成同一个数多次（比如 232323 ）所以要判一下重

　　　　　　只需要把每个数的旋转方式都来一遍，再判一下重，就搞定了（没判重所以来了三十分）

　　上代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 bool st[];//判重用的

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         int a,b,res=,t[],rec[];

         memset(st,false,sizeof(st));

         scanf("%d%d",&a,&b);

         for(int i=a;i<=b;i++)

         {    

             int cnt=,l=a,p=;

             while(l)//看一下有多少位   下面分段用

             {

                 l/=;

                 cnt*=;

             }

             for(int j=;j<cnt;j*=)//枚举从哪一位分段

             {

                 int k=i%j*(cnt/j)+i/j;

                 if(k>=a&&k<i)

                 {

                     if(st[k]) continue;//已经有了就不加了

                     rec[p++]=k;

                     st[k]=true;

                     res++;

                 }

             }

             for(int j=;j<p;j++) st[rec[j]]=false;//把刚刚判的重弄回去

         }

         printf("%d\n",res);

     }

 }

　　　　搞定

　T2 路径数：

　　　　题意：

　　　　　　　　　　Euphemia到一个N*N的药草田里采药，她从左上角的格子田（第一行，第一列）出发，要到达右下角（第N行，第N列）的格子田，每次她可以走到与当前格子有边相邻的格子去，但她不会走已经走过的格子，而且出于对美的要求，她走过的路径是关　　　　　　于左下-右上对角线对称的。由于地势不同，在每个格子田采药都会有一个疲劳度Tij，Euphemia想知道：有多少条合法路径，可以使得她采药的疲劳度最小。

　　　　　输入格式：

　　　　　　　　　　多组数据。
　　　　　　　　　　每组数据第一行一个整数N，接下来N行，每行N个非零数字（1,2,3...9中一个），表示格子田的疲劳度。
　　　　　　　　　　当N=0，输入结束。

　　　　　输出格式：

　　　　　　　　　　对于每组数据，输出一个整数表示答案，答案%1000000009。

　　　　　样例输入：

　　　　　样例输出：

　　　　　　　　　　2

　　　　　　　　　　3

　　　　　数据范围：

　　　　　　　　　　对于20%的数据满足N<=5。
　　　　　　　　　　对于另外20%的数据满足N<=40。
　　　　　　　　　　对于100%的数据满足N<=100,不超过50组数据。

　　大概理解为： 从左上角走到右下角的最短路径方案数，但题目有个路径关于左下-右上对角线对称，大概理解为这样

　　　　　　　　我画的好丑

　　分析：

　　　　　　这个题看出来是单源最短路，N有点大，所以就用堆优化的Dijkstra了然而我竟然用dp来做，才得60

　　　　　　因为有个对称，所以我们只需要把对角线以下的权值全部对称加到对角线以上，再从左上角走到对角线就OK了

　上代码：

 #include<cstdio>

 #include<iostream>

 #include<queue>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N=;

 const int mod=;

 long long dis[N][N];

 int t[N][N],db[N][N];

 int n;

 bool book[N][N];

 struct sik

 {

     int x,y,w;//坐标 权值

     bool operator< (const sik & f) const//重载运算符  使优先队列为小根堆

     {

         return w>f.w;

     }

 };

 int Dijkstra()

 {

     int zx[]={,,,-},zy[]={,,-,};//走的方位    

     memset(dis,0x3f,sizeof(dis));//一堆初始化

     memset(db,,sizeof(db));

     memset(book,false,sizeof(book));

     int res=,Min=0x3f3f3f3f;

     priority_queue<sik> que;//优先队列 

     sik qu;

     dis[][]=t[][];

     db[][]=;

     qu.x=,qu.y=,qu.w=t[][];

     que.push(qu); //把起点放进去 

     while(que.size())

     {

         sik c=que.top();

         que.pop();

         int x=c.x,y=c.y;

         if(dis[x][y]<=Min&&x+y==n+) //到终点了

         {

             if(dis[x][y]==Min) res+=db[x][y];

             else

             {

                 res=db[x][y];

                 Min=dis[x][y];

             }

         }

         if(book[x][y]) continue;//当前点走过了 pass掉

         book[x][y]=false;

         for(int i=;i<;i++)

         {

             int x1=x+zx[i],y1=y+zy[i];

             if(book[x1][y1]||!x1||x1>n||!y1||y1>n) continue;

             if(dis[x1][y1]>dis[x][y]+t[x1][y1])

             {

                 dis[x1][y1]=dis[x][y]+t[x1][y1];

                 db[x1][y1]=db[x][y];

                 sik o;

                 o.x=x1 , o.y=y1 , o.w=dis[x1][y1];//把当前这个点存进去

                 que.push(o);

             }

             else if(dis[x1][y1]==dis[x][y]+t[x1][y1])

             {

                 db[x1][y1]+=db[x][y];

             }

         }

     }

     return res;

 }

 int main()

 {

     while(true)

     {

         memset(t,,sizeof(t));

         scanf("%d",&n);

         if(!n) return ;

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n;j++)

             {

                 scanf("%d",&t[i][j]);

             }

         }

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n-i;j++)

             {

                 t[i][j]+=t[n-j+][n-i+];//把对角线以下的加上去 

             }

         }

         printf("%d\n",Dijkstra());

     }

     return ;

 }

　　搞定

　　T3 ：

　　　　　　不会

　　　~END~

巴特西

【XJOI】NOIP2020模拟训练题2 总结

得分情况：

T1 友好数对：

题意：

输入格式：

输出格式：

样例输入：

样例输出：

数据范围：

分析：

上代码：

T2 路径数：

题意：

输入格式：

输出格式：

样例输入：

样例输出：

数据范围：

上代码：

T3 ：

最新文章

热门文章