2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_1 [2023/07/20 21:54] blackening 创建 |
2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_1 [2023/07/21 19:12] (当前版本) blackening |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ===A=== | ===A=== | ||
| ===B=== | ===B=== | ||
| + | |||
| + | 瞎搞题 | ||
| + | |||
| + | **AC代码** | ||
| + | <code> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | using namespace std; | ||
| + | const int maxn=1e6+5; | ||
| + | ll x[maxn],y[maxn]; | ||
| + | int n; | ||
| + | ll getS(int a[]){ | ||
| + | return abs(x[a[0]]*y[a[1]]-x[a[0]]*y[a[2]]+x[a[1]]*y[a[2]]-x[a[1]]*y[a[0]]+x[a[2]]*y[a[0]]-x[a[2]]*y[a[1]]); | ||
| + | } | ||
| + | int main(){ | ||
| + | scanf("%d",&n); | ||
| + | for(int i=0;i<n;i++){ | ||
| + | scanf("%lld%lld",&x[i],&y[i]); | ||
| + | } | ||
| + | bool f[3]={0,0,0}; | ||
| + | int a[3]={0,n/2,n-1},l=0,r=2,m=1; | ||
| + | ll S=getS(a); | ||
| + | int tmp; | ||
| + | int b[3]={0,1,2}; | ||
| + | while(!f[0]||!f[1]||!f[2]){ | ||
| + | tmp=a[m]; | ||
| + | int to=tmp; | ||
| + | bool flag=0; | ||
| + | a[m]=(tmp+1)%n; | ||
| + | ll tmpS=getS(a); | ||
| + | if(S<tmpS){ | ||
| + | S=tmpS; | ||
| + | to=a[m]; | ||
| + | flag=1; | ||
| + | } | ||
| + | a[m]=(tmp-1+n)%n; | ||
| + | tmpS=getS(a); | ||
| + | if(S<tmpS){ | ||
| + | S=tmpS; | ||
| + | to=a[m]; | ||
| + | flag=1; | ||
| + | } | ||
| + | if(!flag){ | ||
| + | f[m]=1; | ||
| + | }else{ | ||
| + | f[0]=f[1]=f[2]=0; | ||
| + | } | ||
| + | a[m]=to; | ||
| + | b[m]=tmp; | ||
| + | l=(l+1)%3; | ||
| + | r=(r+1)%3; | ||
| + | m=(m+1)%3; | ||
| + | } | ||
| + | cout<<a[0]+1<<" "<<a[1]+1<<" "<<a[2]+1<<endl; | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | |||
| ===C=== | ===C=== | ||
| 行 91: | 行 149: | ||
| </code> | </code> | ||
| ===D=== | ===D=== | ||
| + | 签到题 | ||
| + | |||
| + | **题目大意** | ||
| + | |||
| + | 给定一个n*m的矩阵，两人博弈，每次可以选择一个i<=n,j<=m,所有在i*j矩阵区域内的点都会被访问,每次选择的i,j必须保证新访问一个未被访问过的点,必须要访问最后一个没被访问的点的人输。 | ||
| + | |||
| + | **算法思路** | ||
| + | |||
| + | 考虑在n=1,m=1时一定是后手赢,一行一列的时候一定是先手赢 | ||
| + | |||
| + | 对于更广泛的情况,考虑维护L型,无论后手如何操作,先手一定能维护L型,那么最终后手一定会走到一行一列的状态,因此L型是必败态 | ||
| + | |||
| + | **AC代码** | ||
| + | <code> | ||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | int main(){ | ||
| + | int n,m; | ||
| + | cin>>n>>m; | ||
| + | if(n==1&&m==1) printf("Walk Alone"); | ||
| + | else printf("Kelin"); | ||
| + | } | ||
| + | </code> | ||
| + | |||
| ===E=== | ===E=== | ||
| ===F=== | ===F=== | ||
2023-2024/teams/ikun_is_coding/2023_牛客暑期多校训练营_1.1689861267.txt.gz · 最后更改: 2023/07/20 21:54 由 blackening
