• 2019ICPC南京站

    A

    A Hard Problem

    题意：给定一个正整数 n ，你需要找出最小整数 k，满足：从{1,2,⋯,n}中任意选择长度为k的子集，存在两个不同的整数 u,v∈T, 且 u 是 v 的因数。

    思路：打表找规律 k = \left \lceil n/2 \right \rceil + 1

    1. #include 
    2. #define ios ios::sync_with_stdio(0),cin.tie(0)
    3. #define PII pair
    4. typedef long long ll;
    5. const int N=1e8+10;
    6. const int inf=0x3f3f3f3f;
    7.  
    8. using namespace std;
    9.  
    10. void solve()
    11. {
    12.     int n;
    13.     cin>>n;
    14.     cout<<(n+3)/2<<'\n';
    15. }
    16. signed main()
    17. {
    18.     //freopen("input.txt","r",stdin);
    19.     //freopen("output.txt","w",stdout);
    20.     ios;
    21.     // get();
    22.     // cout<
    23.     int _t=1;
    24.     cin>>_t;
    25.     while(_t--) solve();
    26.     system("pause");
    27.     return 0;
    28. }

    C

    Digital Path

    题意：给定一个n*m的数字矩阵，从入度为0的点出发，每次操作只能向上下左右且增值为1的格子移动，终点为出度为0的点。求长度大于等于4的路径个数。

    思路：先算出每个点的出度入度，从入度为0的开始bfs，更新方案数。

    f[i][j][x]表示到达点(i, j)路径长度为x的方案数，特别的f[i][j][4]表示到达点(i, j)路径长度大于等于4的方案数。更新方式如下：

    f[nx][ny][2] += f[x][y][1]

    f[nx][ny][3] += f[x][y][2]

    f[nx][ny][4] += f[x][y][3] + f[x][y][4]

    1. #include 
    2. #define ios ios::sync_with_stdio(0),cin.tie(0)
    3. #define PII pair
    4.  
    5. typedef long long ll;
    6. const int N=1010;
    7. const int inf=0x3f3f3f3f;
    8. const int mod=1e9+7;
    9. using namespace std;
    10. int n,m;
    11. int a[N][N];
    12. int in[N][N],out[N][N];
    13. int f[N][N][5];
    14. int dir[4][2]={1,0,-1,0,0,1,0,-1};
    15. void bfs()
    16. {
    17.     queueint,int>>q;
    18.     for(int i=1;i<=n;i++)
    19.         for(int j=1;j<=m;j++)
    20.             if(in[i][j]==0) 
    21.             {
    22.                 q.push({i,j});
    23.                 f[i][j][1]=1;
    24.             }
    25.     while(q.size())
    26.     {
    27.         int x=q.front().first,y=q.front().second;
    28.         q.pop();
    29.  
    30.         for(int k=0;k<4;k++)
    31.         {
    32.             int nx=x+dir[k][0],ny=y+dir[k][1];
    33.             if(nx<1||nx>n||ny<1||ny>m) continue;
    34.             if(a[nx][ny]==a[x][y]+1)
    35.             {
    36.                f[nx][ny][2]=(f[nx][ny][2]%mod+f[x][y][1])%mod;
    37.                f[nx][ny][3]=(f[nx][ny][3]%mod+f[x][y][2])%mod;
    38.                f[nx][ny][4]=((f[nx][ny][4]%mod+f[x][y][3]%mod)%mod+f[x][y][4]%mod)%mod;
    39.                in[nx][ny]--; 
    40.                if(in[nx][ny]==0) q.push({nx,ny});
    41.             }
    42.         }
    43.     }
    44. }
    45. void solve()
    46. {
    47.     cin>>n>>m;
    48.     for(int i=1;i<=n;i++)
    49.         for(int j=1;j<=m;j++)
    50.             cin>>a[i][j];
    51.     for(int i=1;i<=n;i++)
    52.         for(int j=1;j<=m;j++)
    53.             for(int k=0;k<4;k++)
    54.             {
    55.                 int nx=i+dir[k][0],ny=j+dir[k][1];
    56.                 if(nx<1||nx>n||ny<1||ny>m) continue;
    57.                 if(a[nx][ny]==a[i][j]+1) out[i][j]++;
    58.                 else if(a[nx][ny]==a[i][j]-1) in[i][j]++;
    59.             }
    60.     
    61.     bfs();
    62.  
    63.     int ans=0;
    64.     for(int i=1;i<=n;i++)
    65.         for(int j=1;j<=m;j++)
    66.             if(out[i][j]==0) ans=(ans%mod+f[i][j][4])%mod;
    67.     cout<'\n';
    68. }
    69. signed main()
    70. {
    71.     //freopen("input.txt","r",stdin);
    72.     //freopen("output.txt","w",stdout);
    73.     ios;
    74.     int _t=1;
    75.     //cin>>_t;
    76.     while(_t--) solve();
    77.     system("pause");
    78.     return 0;
    79. }

    H

    Prince and Princess

    题意：

    有n个房间,每个房间有一个人,他们知道任一个人在哪个房间,其中公主在某一房间.你可以问任一房间的人下列三个问题之一:①你是谁;②某个房间里的人是谁;③公主在哪个房间.

    这n个人可分为三类,说真话、说假话、可能说真话也可能说假话,分别有a , b , c( 0 < a , b , c < 2e5 )人.至少问几次才能确定公主在哪个房间.若无法确定,输出"NO";若可以确定,输出"YES",下一行输出最小询问次数.

    思路：考虑最坏情况，开始问的(b+c)个人都说假话，都回答错误答案A，再接着问(b+c)个人都说真话，都回答答案B，此时两个答案选择人数相同；再多问一个人，就可以区分出哪个是真话。所以至少需要问a+b+a+b+1=2(a+b)+1次，当总人数a+b+c >= 2(b+c)+1时，即a>=b+c+1时，输出YES。注意需要特判a=1 b=0 c=0时，只有公主一人时不需要询问。

    1. #include 
    2. #define ios ios::sync_with_stdio(0),cin.tie(0)
    3. #define PII pair
    4. typedef long long ll;
    5. const int N=1e6+10;
    6. const int inf=0x3f3f3f3f;
    7.  
    8. using namespace std;
    9. int a,b,c;
    10. void solve()
    11. {
    12.     cin>>a>>b>>c;
    13.     if(b+c>=a) cout<<"NO\n";
    14.     else 
    15.     {
    16.         cout<<"YES\n";
    17.         if(a==1&&b==0&&c==0) cout<<0<<'\n';
    18.         else if(b==0&&c==0) cout<<1<<'\n';
    19.         else cout<<2*(b+c)+1<<'\n';
    20.     }
    21. }
    22. signed main()
    23. {
    24.     //freopen("input.txt","r",stdin);
    25.     //freopen("output.txt","w",stdout);
    26.     ios;
    27.     int _t=1;
    28.     //cin>>_t;
    29.     while(_t--) solve();
    30.     system("pause");
    31.     return 0;
    32. }

    K

    Triangle

    题意：给定三角形三个顶点的坐标，给定点p，在三角形上找一点q的坐标，使得pq可以平分三角形面积。若p点不在三角形上时输出-1.

    思路：分类讨论，讨论p在哪条边上，更靠近边的哪个顶点，在对应的边上二分求点q

    1. #include 
    2. #define ios ios::sync_with_stdio(0),cin.tie(0)
    3. #define PII pair
    4. typedef long long ll;
    5. const int N=1e6+10;
    6. const int inf=0x3f3f3f3f;
    7. const double eps=1e-7;
    8. using namespace std;
    9. inline double sqr(double x){return x*x;}
    10. int sgn(double x){
    11.     if(fabs(x) < eps)return 0;
    12.     if(x < 0)return -1;
    13.     else return 1;
    14. }
    15.  
    16. struct Point{
    17.     double x,y;
    18.     Point(){}
    19.     Point(double _x,double _y){
    20.         x = _x;
    21.         y = _y;
    22.     }
    23.     void input(){
    24.         scanf("%lf%lf",&x,&y);
    25.     }
    26.  
    27.     Point operator -(const Point &b)const{
    28.         return Point(x-b.x,y-b.y);
    29.     }
    30.     //叉积
    31.     double operator ^(const Point &b)const{
    32.         return x*b.y - y*b.x;
    33.     }
    34.     //点积
    35.     double operator *(const Point &b)const{
    36.         return x*b.x + y*b.y;
    37.     }
    38.  
    39.     //返回两点的距离
    40.     double distance(Point p){
    41.         return hypot(x-p.x,y-p.y);
    42.     }
    43.     Point operator +(const Point &b)const{
    44.         return Point(x+b.x,y+b.y);
    45.     }
    46.     Point operator *(const double &k)const{
    47.         return Point(x*k,y*k);
    48.     }
    49.  
    50. };
    51.  
    52.  
    53. struct Line{
    54.     Point s,e;
    55.     Line(){}
    56.     Line(Point _s,Point _e){
    57.         s = _s;
    58.         e = _e;
    59.     }
    60.  
    61.     // 点在线段上的判断
    62.     bool pointonseg(Point p){
    63.         return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
    64.     }
    65.    
    66. };
    67.  
    68. Point mid_(Point a, Point b)
    69. {
    70. 	return (a+b)*0.5;
    71. }
    72.  
    73. double area(Point a, Point b, Point c)
    74. {
    75. 	return fabs((b - a) ^ (c - a) * 0.5);
    76. }
    77.  
    78. void solve()
    79. {
    80.     Point a,b,c,p;
    81.     Line ab,ac,bc;
    82.     a.input();
    83.     b.input();
    84.     c.input();
    85.     p.input();
    86.     ab=Line(a,b);
    87.     ac=Line(a,c);
    88.     bc=Line(b,c);
    89.     if(!ab.pointonseg(p)&&!ac.pointonseg(p)&&!bc.pointonseg(p))
    90.     {
    91.         printf("-1\n");
    92.     }
    93.     else
    94.     {
    95.         double s=area(a,b,c)/2;
    96.         if(ab.pointonseg(p))
    97.         {
    98.             double dispa=p.distance(a);
    99.             double dispb=p.distance(b);
    100.             if(dispa
    101.             {
    102.                 Point l=b,r=c;
    103.                 Point mid;
    104.                 int x=50;
    105.                 while(x--)
    106.                 {
    107.                     mid=mid_(l,r);
    108.                     int ret=sgn(area(mid,p,b)-s);
    109.                     if(ret>0) r=mid;
    110.                     else if(ret<0) l=mid;
    111.                     else break;
    112.                 }
    113.                 printf("%.10f %.10f\n",mid.x,mid.y);
    114.             }
    115.             else
    116.             {
    117.                 Point l=a,r=c;
    118.                 Point mid;
    119.                 int x=50;
    120.                 while(x--)
    121.                 {
    122.                     mid=mid_(l,r);
    123.                     int ret=sgn(area(mid,p,a)-s);
    124.                     if(ret>0) r=mid;
    125.                     else if(ret<0) l=mid;
    126.                     else break;
    127.                 }
    128.                 printf("%.10f %.10f\n",mid.x,mid.y);
    129.             }
    130.         }
    131.         else if(ac.pointonseg(p))
    132.         {
    133.             double dispa=p.distance(a);
    134.             double dispc=p.distance(c);
    135.             if(dispa
    136.             {
    137.                 Point l=c,r=b;
    138.                 Point mid;
    139.                 int x=50;
    140.                 while(x--)
    141.                 {
    142.                     mid=mid_(l,r);
    143.                     int ret=sgn(area(p,mid,c)-s);
    144.                     if(ret>0) r=mid;
    145.                     else if(ret<0) l=mid;
    146.                     else break;
    147.                 }
    148.                 printf("%.10f %.10f\n",mid.x,mid.y);
    149.             }
    150.             else
    151.             {
    152.                 Point l=a,r=b;
    153.                 Point mid;
    154.                 int x=50;
    155.                 while(x--)
    156.                 {
    157.                     mid=mid_(l,r);
    158.                     int ret=sgn(area(p,mid,a)-s);
    159.                     if(ret>0) r=mid;
    160.                     else if(ret<0) l=mid;
    161.                     else break;
    162.                 }
    163.                 printf("%.10f %.10f\n",mid.x,mid.y);
    164.             }
    165.         }
    166.         else
    167.         {
    168.             double dispb=p.distance(b);
    169.             double dispc=p.distance(c);
    170.             if(dispb
    171.             {
    172.                 Point l=c,r=a;
    173.                 Point mid;
    174.                 int x=50;
    175.                 while(x--)
    176.                 {
    177.                     mid=mid_(l,r);
    178.                     int ret=sgn(area(p,mid,c)-s);
    179.                     if(ret>0) r=mid;
    180.                     else if(ret<0) l=mid;
    181.                     else break;
    182.                 }
    183.                 printf("%.10f %.10f\n",mid.x,mid.y);
    184.             }
    185.             else
    186.             {
    187.                 Point l=b,r=a;
    188.                 Point mid;
    189.                 int x=50;
    190.                 while(x--)
    191.                 {
    192.                     mid=mid_(l,r);
    193.                     int ret=sgn(area(p,mid,b)-s);
    194.                     if(ret>0) r=mid;
    195.                     else if(ret<0) l=mid;
    196.                     else break;
    197.                 }
    198.                 printf("%.10f %.10f\n",mid.x,mid.y);
    199.             }
    200.         }
    201.     }
    202. }
    203. signed main()
    204. {
    205.     //freopen("input.txt","r",stdin);
    206.     //freopen("output.txt","w",stdout);
    207.     ios;
    208.     int _t=1;
    209.     // cin>>_t;
    210.     scanf("%d",&_t);
    211.     while(_t--) solve();
    212.     system("pause");
    213.     return 0;
    214. }

    J

    Spy

    题意：给定n个敌人的力量值a[i]，及击杀敌人获得的荣誉值p[i].给定你的第一队的力量值b[i]，第二队的力量值c[i].需要将b[i]与c[j]一一配对后组成n只队伍d[]，新的力量值为两人之和，d[]再与a[]随机战斗，每只队伍只能战斗一次，共n!种情况。若d[i]>a[i]我方获得荣誉值p[i].求可获得的荣誉的最大期望乘n的值，数据保证最大期望乘n后是整数

    思路：把b[]和c[]当作二分图，边的权值为这对组合可以获得的荣誉值之和。然后进行KM算法，找到最大权值匹配即为答案。

    1. #include 
    2. #define ios ios::sync_with_stdio(0),cin.tie(0)
    3. #define PII pair
    4. typedef long long ll;
    5. const int N=410;
    6. const int inf=0x3f3f3f3f;
    7. const ll infll=1e15+7;
    8. using namespace std;
    9. int n;
    10. ll a[N],p[N],b[N],c[N];
    11. ll w[N][N];
    12. ll la[N], lb[N], upd[N]; // 左、右部点的顶标
    13. bool va[N], vb[N]; // 访问标记：是否在交错树中
    14. ll match[N]; // 右部点匹配了哪一个左部点
    15. ll last[N]; // 右部点在交错树中的上一个右部点，用于倒推得到交错路
    16.  
    17. bool dfs(ll x, ll fa) 
    18. {
    19.     va[x] = 1;
    20.     for(int y = 1; y <= n; y++)
    21.     {
    22. 		if(!vb[y])
    23.         {
    24. 			if(la[x] + lb[y] == w[x][y]) 
    25. 			{ 
    26.                 vb[y] = 1; last[y] = fa;
    27.                 if(!match[y] || dfs(match[y], y)) 
    28. 				{
    29.                     match[y] = x;
    30.                     return true;
    31.                 }
    32.             }
    33.             else if(upd[y] > la[x] + lb[y] - w[x][y]) 
    34. 			{
    35.                 upd[y] = la[x] + lb[y] - w[x][y];
    36.                 last[y] = fa;
    37.             }
    38. 		}
    39. 	}
    40.     return false;
    41. }
    42.  
    43. ll KM() 
    44. {
    45.     for(int i = 1; i <= n; i++) 
    46. 	{
    47.         la[i] = -infll;
    48.         lb[i] = 0;
    49.         for(int j = 1; j <= n; j++) la[i] = max(la[i], w[i][j]);
    50.     }
    51.     for(int i = 1; i <= n; i++) 
    52. 	{
    53.         memset(va, 0, sizeof(va));
    54.         memset(vb, 0, sizeof(vb));
    55.         for(int j = 1; j <= n; j++) upd[j] = infll;
    56.         // 从右部点st匹配的左部点match[st]开始dfs，一开始假设有一条0-i的匹配
    57.         int st = 0; match[0] = i;
    58.         while(match[st]) 	// 当到达一个非匹配点st时停止
    59. 		{ 
    60.             ll delta = infll;
    61.             if(dfs(match[st], st)) break;
    62.             for(int j = 1; j <= n; j++)
    63.                 if(!vb[j] && delta > upd[j]) 
    64. 				{
    65.                     delta = upd[j];
    66.                     st = j; 		// 下一次直接从最小边开始DFS
    67.                 }
    68.             for(int j = 1; j <= n; j++)  // 修改顶标
    69. 			{
    70.                 if(va[j]) la[j] -= delta;
    71.                 if(vb[j]) lb[j] += delta; 
    72. 				else upd[j] -= delta;
    73.             }
    74.             vb[st] = true;
    75.         }
    76.         while(st)	// 倒推更新增广路 
    77. 		{ 
    78.             match[st] = match[last[st]];
    79.             st = last[st];
    80.         }
    81.     }
    82. 	ll ans = 0;
    83. 	for(int i = 1; i <= n; i++) 
    84. 		if(match[i]) 
    85. 			ans += w[match[i]][i];
    86. 	return ans;
    87. }
    88.  
    89. void solve()
    90. {
    91.     cin>>n;
    92.     for(int i=1;i<=n;i++) cin>>a[i];
    93.     for(int i=1;i<=n;i++) cin>>p[i];
    94.     for(int i=1;i<=n;i++) cin>>b[i];
    95.     for(int i=1;i<=n;i++) cin>>c[i];
    96.  
    97.     for(int i=1;i<=n;i++)
    98.         for(int j=1;j<=n;j++)
    99.         {
    100.             ll sum=0;
    101.             for(int k=1;k<=n;k++)
    102.                 if(b[i]+c[j]>a[k]) sum+=p[k];
    103.             w[i][j]=sum;
    104.         }
    105.     cout<<KM()<<'\n';
    106.     
    107. }
    108. signed main()
    109. {
    110.     //freopen("input.txt","r",stdin);
    111.     //freopen("output.txt","w",stdout);
    112.     ios;
    113.     int _t=1;
    114.     //cin>>_t;
    115.     while(_t--) solve();
    116.     system("pause");
    117.     return 0;
    118. }

  • 相关阅读:
    Thinkphp 5.0.24变量覆盖漏洞导致RCE分析
    【OBS】circlebuf
    耶幕上门推拿平台系统开发解析
    c 两进程（多进程）通过mmap()共享内存通信
    多点DMALL × Apache Kyuubi：构建统一SQL Proxy探索实践
    Windows任务管理器命令行查进程
    聚焦创新丨赛宁网安亮相2022未来网络发展大会成果展
    怎么合并多个PDF文件？快进来学习PDF的合并办法
    Springboot 项目下载资源目录下的 Word 文件
    多线程与线程池
  • 原文地址：https://blog.csdn.net/qq_62615329/article/details/134539480