• 2022“杭电杯”中国大学生算法设计超级联赛（1）(6题newbie,后续会更新)

    1002 Dragon slayer(搜索,签到)

    思路:因为数据很水,我们可以直接硬搜,bfs的每个节点里记录一下每面墙是否被破坏.每次移动判断一下我是否要打破墙即可.

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6. typedef vector<int> vec;
    7. int n,m,k,sx,sy,tx,ty;
    8. int dx[] = {1,0,-1,0};
    9. int dy[] = {0,1,0,-1};
    10. struct node
    11. {
    12.     int s,x,y;
    13.     int w[16];
    14.     void init(){
    15.         for(int i=1;i<=k;i++)w[i] = 0;
    16.     }
    17.     bool operator < (const node &A)const{
    18.         return s > A.s;
    19.     }
    20. };
    21. struct edge
    22. {
    23.     int x1,y1,x2,y2;
    24. }e[20];
    25. bool st[20][20];
    26. priority_queueq;
    27. void bfs()
    28. {
    29.     while(!q.empty())q.pop();
    30.  
    31.     node sta = {0,sx,sy};
    32.     sta.init();
    33.     q.push(sta);
    34.     while(!q.empty())
    35.     {
    36.         node p = q.top();
    37.         q.pop();
    38.         int x = p.x, y = p.y;
    39.         if(st[x][y]) continue ;
    40.  
    41.         // printf("x = %d y = %d p.s = %d\n",x,y,p.s);
    42.  
    43.         if(x == tx && y == ty)
    44.         {
    45.             printf("%d\n",p.s);
    46.             break;
    47.         }
    48.  
    49.         st[x][y] = 1;
    50.         for(int i=0;i<4;i++)
    51.         {
    52.             int r = x + dx[i], c = y + dy[i];
    53.             if(r < 0 || r >= n || c < 0 || c >= m || st[r][c]) continue ;
    54.             // printf("r = %d c = %d\n",r,c);
    55.             node nex = p;
    56.             int x1,y1,x2,y2;
    57.             if(i == 0)//x + 1
    58.             {
    59.                 x1 = x2 = r;
    60.                 y1 =  y, y2 = y + 1;
    61.             }
    62.             else if(i == 1)//y + 1
    63.             {
    64.                 y1 = y2 = c;
    65.                 x1 = x, x2 = x + 1;
    66.             }
    67.             else if(i == 2)//x - 1
    68.             {
    69.                 x1 = x2 = x;
    70.                 y1 = y, y2 = y + 1;
    71.             }
    72.             else//y - 1
    73.             {
    74.                 y1 = y2 = y;
    75.                 x1 = x,x2 = x + 1;
    76.             } 
    77.  
    78.             for(int j=1;j<=k;j++)
    79.             {
    80.                 if(p.w[j]) continue ;
    81.                 if(x1 < e[j].x1 || x1 > e[j].x2 || x2 < e[j].x1 || x2 > e[j].x2) continue ;
    82.                 if(y1 < e[j].y1 || y1 > e[j].y2 || y2 < e[j].y1 || y2 > e[j].y2) continue ;
    83.                 nex.s ++;
    84.                 nex.w[j] = 1;
    85.             }
    86.             nex.x = r, nex.y = c;
    87.             q.push(nex);
    88.         }
    89.     }
    90. }
    91. void init(int id)
    92. {
    93.     int x1,x2,y1,y2;
    94.     scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    95.     if(x1 > x2)swap(x1,x2);
    96.     if(y1 > y2)swap(y1,y2);
    97.     e[id] = {x1,y1,x2,y2};
    98. }
    99. void solve()
    100. {
    101.     scanf("%d%d%d",&n,&m,&k);
    102.     scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    103.  
    104.     for(int i=0;i<=n;i++)
    105.     for(int j=0;j<=m;j++) st[i][j] = 0;
    106.  
    107.     for(int i=1;i<=k;i++) init(i);
    108.     bfs();
    109.     return ;
    110. }
    111. int main()
    112. {
    113.     int T;
    114.     scanf("%d",&T);
    115.     while(T--)solve();
    116.     return 0;
    117. }

    1003 Backpack(bitset优化,背包)

    给定n个物品和体积为m的背包，物品有体积和价值。要求选择若干个物品填满背包，并且使得物品价值的异或和最大。

    首先既然是背包dp,就先写出状态,f [ i ][ j ][ k ]表示三层含义,但是由于最大异或和没有最优子结构的性质,就不能作为最后一维的状态,那么i就表示在采用前i中物品的情况下,能够组成异或和为j的体积为k的方法是否存在,然后直接按照01背包,选与不选进行状态转移.但是由于n的3次方不仅宝空间也爆时间,又因为最后一维里面的值只包含0,1,所以想到用bitset来优化(具体用法不细说).bitset的特性可以让这个01数组的空间和时间都除以32.

    1. #include
    2. #define int long long
    3. using namespace std;
    4. const int N =5e5+10,mod=998244353;
    5. int v[2000],w[2000];
    6. bitset<1024>f[2][2000];
    7. void solve()
    8. {
    9.     int n,m;
    10.     cin>>n>>m;
    11.     for(int i=1;i<=n;i++)
    12.         cin>>v[i]>>w[i];
    13.     for(int i=0;i<1024;i++) 
    14.         f[0][i].reset();  
    15.     f[0][0].set(0);
    16.     for(int i=1;i<=n;i++)
    17.         for(int j=0;j<1024;j++)
    18.             f[i&1][j]=(f[(i&1)^1][j])|(f[(i&1)^1][j^w[i]]<
    19.     int ans=0;
    20.     for(int i=1023;i>=0;i--)
    21.         if(f[n&1][i][m])
    22.         {
    23.             cout<"\n";
    24.             return ;
    25.         }
    26.     cout<<"-1\n";
    27.     return ;
    28. }
    29. signed main()
    30. {
    31.     cin.tie(0);
    32.     cout.tie(0);
    33.     ios::sync_with_stdio(0);
    34.     int t;
    35.     cin>>t;
    36.     while(t--)
    37.        solve();
    38.     return 0;
    39. }

    1004 Ball(bitset优化,枚举)

    思路:我们先吧每一条边都存起来,并且从小到大排个序(排序目的是避免后面的运算重复)然后对边进行遍历.当遍历的边是素数长度是进行一次check(这里判断是否为素数直接欧拉筛就行,数据范围1e5).

    此时我们已经枚举了两个点并且确定了一条素数边了.那么如果要对答案做出贡献的话,剩余的点必须满足和之前选出的两个点的两条边一条大于素数边,一条小于素数边.用一个bitset维护来维护点集bitset<2048>visit[2048];第一维的状态表示一个点,第二维为01状态表示第一维的点和和第二维的下标组成的线段是否被遍历过了.

    我们就将作为素数边的端点的两个点去找他们的相交的线段是否是一长一短,这个时候就可以考虑把遍历过的线段进行标记(用bitset置为1).那么下方代码中

    visit[edg[i].po1]^visit[edg[i].po2]

    的意思就是看选的第三个端点和两个素数边端点组成的端点的状况.如果是一长一短,因为是从小到大排列,而且遍历的也在bitset中置为1,所以只要满足这个式子结果为1,也就是一个遍历过一个没有遍历,就可以满足条件,得到1的数量就是可以组成的个数.

    1. #include
    2. #define int long long
    3. using namespace std;
    4. const int N =5e5+10,mod=998244353;
    5. bitset<2048>visit[2048];
    6. /*
    7. bitset存边,遍历过的即为1,未遍历即为0,只需要把边长度处理出来
    8. 之后排序(从小到大,这样就可以保证遍历过的边和没遍历过的在不同状态,bitset标记),
    9. 然后遍历,当该边为质数是用bitset进行异或(比他小的已经遍历了).结果加起来即可
    10. */
    11. struct point
    12. {
    13.     int x,y;
    14. }poi[2048];
    15. struct edge
    16. {
    17.     int po1,po2,len;
    18. }edg[5001000];
    19. int vis[200100],p[100100],cnt=0;
    20. void init()
    21. {
    22.     vis[0]=vis[1]=1;
    23.     for(int i=2;i<=200005;i++)
    24.     {
    25.         if(!vis[i])
    26.             p[++cnt]=i;
    27.         for(int j=1;j<=cnt&&i*p[j]<=200005;j++)
    28.         {
    29.             vis[i*p[j]]=1;
    30.             if(i%p[j]==0)
    31.                 break;
    32.         }
    33.     }
    34. }
    35. void solve()
    36. {
    37.     int n,m;
    38.     cin>>n>>m;
    39.     
    40.     for(int i=1;i<=n;i++)
    41.         cin>>poi[i].x>>poi[i].y,visit[i].reset();
    42.     int tot=0;
    43.     for(int i=1;i<=n;i++)
    44.     {
    45.         for(int j=i+1;j<=n;j++)
    46.         {
    47.             edg[++tot].po1=i;
    48.             edg[tot].po2=j;
    49.             edg[tot].len=abs(poi[i].x-poi[j].x)+abs(poi[i].y-poi[j].y);
    50.         }
    51.     }   
    52.     sort(edg+1,edg+tot+1,[&](edge a,edge b){  
    53.         return a.len
    54.     });  
    55.     int ans=0;
    56.     for(int i=1;i<=tot;i++)
    57.     {
    58.         if(vis[edg[i].len]==0)
    59.         {
    60.             ans+=(visit[edg[i].po1]^visit[edg[i].po2]).count();
    61.         }
    62.         visit[edg[i].po1].set(edg[i].po2);
    63.         visit[edg[i].po2].set(edg[i].po1);
    64.     }
    65.     cout<
    66.     return ;
    67. }
    68. signed main()
    69. {
    70.     cin.tie(0);
    71.     cout.tie(0);
    72.     ios::sync_with_stdio(0);
    73.     init();
    74.     int t;
    75.     cin>>t;
    76.     while(t--)
    77.        solve();
    78.     return 0;
    79. }

    1009 Laser(计算几何,枚举)

    判断特殊情况+计算几何知识运用

    1. #include
    2. #define ll long long
    3. using namespace std;
    4. #define B cerr<<"Break Point"<
    5. #define pl(x) cerr<<#x<<' '<<"="<<' '<<(x)<
    6. #define p(x) cerr<<#x<<' '<<"="<<' '<<(x)<<' ';
    7. namespace io{
    8.     const int SIZ=55;
    9.     int que[SIZ],op,qr;
    10.     char ch;
    11.     template<class I>
    12.     void read(I &w){
    13.         ch=getchar(),op=1,w=0;
    14.         while(!isdigit(ch)){if(ch=='-') op=-1;ch=getchar();}
    15.         while(isdigit(ch)){w=w*10+ch-'0';ch=getchar();}w*=op;
    16.     }
    17.     template<typename T,typename... Args>
    18.     void read(T& t,Args&... args){read(t);read(args...);}
    19. }
    20. using io::read;
    21. const int N=5e5+5;
    22. int T,n;
    23. struct node{
    24.     int x,y;
    25. };
    26. node p[N];
    27. bool Check(int ox,int oy)
    28. {
    29.     bool flag=true;
    30. 	for (int i = 1; i <= n; ++i)
    31. 	{
    32.         if(p[i].x == ox) continue;
    33.         if(p[i].y == oy) continue;
    34. 		if (abs(ox - p[i].x) == abs(oy - p[i].y)) continue;
    35. 		flag = false;
    36. 	}
    37.     return flag;
    38. }
    39. int main()
    40. {
    41.     read(T);
    42.     while(T--)
    43. 	{
    44.         read(n);
    45. 		for (int i = 1; i <= n; ++i)
    46. 			read(p[i].x, p[i].y);
    47. 		bool flag = true;
    48. 		int cur1, cur2;
    49. 		for (int i = 2; i <= n; ++i)
    50. 		{
    51.             if(p[1].x == p[i].x) continue;
    52.             if(p[1].y == p[i].y) continue;
    53.             if(abs(p[1].x - p[i].x) == abs(p[1].y - p[i].y)) continue;//判断是否在写对角线上
    54. 			flag = false, cur1 = 1, cur2 = i;
    55. 		}
    56.         if(flag)
    57. 		{
    58.             puts("YES");
    59.             continue;
    60.         }
    61. 		int X1 = p[cur1].x, Y1 = p[cur1].y, X2 = p[cur2].x, Y2 = p[cur2].y;
    62. 		flag |= Check(X1, Y2);
    63. 		flag |= Check(X1, X1 - X2 + Y2);
    64. 		flag |= Check(X1, -X1 + X2 + Y2);
    65. 		flag |= Check(X2, Y1);
    66. 		flag |= Check(X2 + Y1 - Y2, Y1);
    67. 		flag |= Check(X2 - Y1 + Y2, Y1);
    68. 		flag |= Check(X2, -X1 + X2 + Y1);
    69. 		flag |= Check(X1 - Y1 + Y2, Y2);
    70. 		flag |= Check((X1 + X2 + Y2 - Y1) / 2, (-X1 + X2 + Y1 + Y2) / 2);
    71. 		flag |= Check(X2, X1 - X2 + Y1);
    72. 		flag |= Check(X1 + Y1 - Y2, Y2);
    73. 		flag |= Check((X1 + X2 + Y1 - Y2) / 2, (X1 - X2 + Y1 + Y2) / 2);
    74.         //十二个相交硬判断
    75. 		if(flag) puts("YES");
    76. 		else puts("NO");
    77. 	}
    78.     return 0;
    79. }

    1011 Random(签到)

    1. #include 
    2. #include 
    3. using namespace std;
    4. #define ll long long
    5. const int MOD = 1e9 + 7;
    6. ll ksm(ll a,ll b)
    7. {
    8.     ll ans = 1;
    9.     while(b)
    10.     {
    11.         if(b & 1) ans = ans * a % MOD;
    12.         a = a * a % MOD;
    13.         b >>= 1;
    14.     }
    15.     return ans;
    16. }
    17. ll b;
    18. void solve()
    19. {
    20.     ll n,m;
    21.     cin >> n >> m;
    22.     ll a = n - m;
    23.     // if(a % 2 == 0)
    24.     // {
    25.     //     printf("%lld\n",a / 2);
    26.     // }
    27.     // else
    28.     // {
    29.         printf("%lld\n",a * b % MOD);
    30.     // }
    31.     return ;
    32. }
    33. int main()
    34. {
    35.     int T;
    36.     b = ksm(2,MOD-2);
    37.     scanf("%d",&T);
    38.     while(T--) solve();
    39.     return 0;
    40. }

    1012 Alice and Bob

    思路:可以把两个n看做一个(n-1),一次变化,最后看1的数量即可,如果1的个数大于1就是Alice硬,反之bob.

    1. #include
    2. #define int long long
    3. using namespace std;
    4. const int N =5e5+10,mod=998244353;
    5. int a[1001006];
    6. void solve()
    7. {
    8.     int n;
    9.     cin>>n;
    10.     memset(a,0,n+10);
    11.     for(int i=0;i<=n;i++)
    12.         cin>>a[i];
    13.     if(a[0]!=0)
    14.     {
    15.         cout<<"Alice\n";
    16.         return ;
    17.     }
    18.     for(int i=n;i>1;i--)
    19.     {
    20.         int ans = a[i] / 2;
    21.         a[i - 1] += ans;
    22.     }
    23.     if(a[1]> 1)
    24.     {
    25.         cout<<"Alice\n";
    26.         return ;
    27.     }
    28.     cout<<"Bob\n";
    29.     return ;
    30. }
    31. signed main()
    32. {
    33.     int t;
    34.     cin>>t;
    35.     while(t--)
    36.        solve();
    37.     return 0;
    38. }

  • 相关阅读:
    rpm 系 linux 系统中 /etc/yum.repo.d/ 目录下的 .repo 文件中的 $releasever 到底等于多少？
    MASA Stack 第五期社区例会
    Java OpenJDK 8u392 Windows x64
    vulnhub靶场之WORST WESTERN HOTEL: 1
    基于JAVA全国消费水平展示平台计算机毕业设计源码+系统+mysql数据库+lw文档+部署
    【考研数学】四. 多元函数微积分
    Ant-Maven-Gradle
    DERT：End-to-End Object Detection with Transformers
    Vue项目中强制刷新页面的方法
    分布式概念：编码一个简单分布式系统
  • 原文地址：https://blog.csdn.net/qq_49593247/article/details/126055971