【过题记录】 8.2 hddx

飞行棋

关于这一题
我在考场上手莫了n=2和n=3的情况
发现一点规律，大力猜想蒙了一个结论
结果蒙对了…

关于正确做法，发现零号点和其他几个点是不一样的。
因为对于0而言，他没有赠送的情况(只要摇到n就直接胜利)
因此0和其他点要分开讨论
对于1到n-1号点
他们花费1代价走到n的期望是$1/(n-1)$
因此总的期望代价就是$n-1$步
不难得出$f_0=1/n\ast \sum (fi)+1$
结合上面，得出最终$f_0=(n-1)\ast (n-1)/n+1$

#include<bits/stdc++.h>
using namespace std;#define int long longconst int P = 1e9+7;int Power(int x,int y){int s = 1;while (y){if (y&1) s = s*x%P;x = x*x%P;y>>=1;}return s;
}signed main(){int t; cin>>t;while (t--){int n; cin>>n;int ans = (n-1)*(n-1)%P;ans = (ans+n)%P;ans = ans*Power(n,P-2)%P;cout<<ans<<endl;}return 0;
} 

开关灯

关于这一题
老老实实推了20分钟发现推不出来
“要不打表吧”
秒了…
如果$n\%3==0$，答案就是$2^n$
否则就是$2^{n/3\ast 3+1}$

#include<bits/stdc++.h>
using namespace std;#define int long long
const int P = 998244353;int Power(int x,int y){int s = 1;while (y){if (y&1) s = s*x%P;x = x*x%P;y>>=1;}return s;
}signed main(){int t; cin>>t;while (t--){int x; cin>>x;int a = 0;if (x%3 == 0)a = x;else a = (x/3*3)+1;cout<<Power(2,a)<<endl;}return 0;
}

猫罐头游戏

$打表$找了一下规律
发现奇奇奇必败
有一奇一偶必胜态
唯一要讨论的就是三个偶数的情况
$仔细观察打表数据$
发现对于三个偶数$a,b,c$
将他们一直/2，直到有一个数为奇数
然后再按上面的奇偶性讨论即可。

#include<bits/stdc++.h>
using namespace std;
int T,a,b,c,jsq; 
int main(){scanf("%d",&T);while (T--){scanf("%d%d%d",&a,&b,&c);if (a==b&&b==c){printf("NO\n");continue; }jsq=(a%2)+(b%2)+(c%2);if (jsq==3){printf("NO\n");continue;}if (jsq==1||jsq==2){printf("YES\n");continue;}while (a%2==0&&b%2==0&&c%2==0){a/=2;b/=2;c/=2;}	jsq=(a%2)+(b%2)+(c%2);if (jsq==3){printf("NO\n");continue;}if (jsq==1||jsq==2){printf("YES\n");continue;}printf("YES\n");}return 0;
}

Array-Gift

不难得出
答案就只有三种情况
$n-1$,$n$,$n+1$
而且我们发现，想要变0，只有操作1能让数变0
所以$n-1$的情况是：有一个数为其他所有数的公因数
且只有这么一种情况。

$n$的情况比较多：
1、能找出一个$x=a_i\%a_j$，使x为其他所有数的因数
2、能找出一个数x，使得$a_i+x$为其他所有书的公因数
3、将所有数先按照操作1能变0的变成0，再按照1,2操作讨论

否则就是n+1

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8, pi = acos(-1.0);
int t, a[110];
bool vis[110];
int b[110],m;
int gcd(int a, int b)
{return !b ? a : gcd(b, a % b);
}
int array_gcd(int l, int r, int x)
{int res;if(l==x)res = a[l + 1];elseres = a[l];for (int i = l; i <= r; i++){if (i == x)continue;res = gcd(res, a[i]);}return res;
}
void solve()
{int n, res; m = 0;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];if(n==1){cout << 0 << endl;return;}sort(a + 1, a + n + 1);int jsq = 0;for (int i = 1; i <= n; i++) vis[i] = 0;for (int i = 1; i <= n; i++) if(!vis[i])for (int j = 1; j <= n; j++){if (i == j) continue;if (a[i]%a[j] == 0 && vis[j] == 0){vis[i] = 1;  jsq++; break;}}for (int i = 1; i <= n; i++) if (!vis[i]) b[++m] = a[i];for (int i = 1; i <= m; i++) a[i] = b[i]; n = m;if (n == 1){cout<<jsq<<endl;return;}// 第一种情况int cnt = 0;for (int i = 2; i <= n; i++)if (a[i] % a[1] == 0)cnt++;
//    cout<<"cnt = "<<cnt<<endl;if (cnt == n - 1){cout << jsq+n - 1 << endl;return;}// 第二种情况// a[i]%a[j]==1for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (i == j)continue;if (a[i] % a[j] == 1){cout << jsq+n << endl;return;}}}// a[1]+x==array_gcd(2,n,0);res = array_gcd(2, n, 0);if (res > a[1] && res != 1){cout << jsq+n << endl;return;}// a[i]%a[j]==array_gcd(1,n,i)for (int i = 1; i <= n; i++){res = array_gcd(1, n, i);for (int j = 1; j <= n; j++){if (a[i] % a[j] == res){cout << jsq+n << endl;return;}}}// 第三种情况cout << jsq+n + 1 << endl;
}
signed main()
{// #ifndef ONLINE_JUDGE//     freopen("D:/in.txt","r",stdin);//     freopen("D:/out.txt", "w", stdout);// #endifios::sync_with_stdio(false);cin >> t;while (t--)solve();return 0;
}
/*
100
5
4 11 17 18 16
*/