飞行棋
关于这一题
我在考场上手莫了n=2和n=3的情况
发现一点规律,大力猜想蒙了一个结论
结果蒙对了…
关于正确做法,发现零号点和其他几个点是不一样的。
因为对于0而言,他没有赠送的情况(只要摇到n就直接胜利)
因此0和其他点要分开讨论
对于1到n-1号点
他们花费1代价走到n的期望是 1 / ( n − 1 ) 1/(n-1) 1/(n−1)
因此总的期望代价就是 n − 1 n-1 n−1步
不难得出 f 0 = 1 / n ∗ ∑ ( f i ) + 1 f_0=1/n*\sum(fi)+1 f0=1/n∗∑(fi)+1
结合上面,得出最终 f 0 = ( n − 1 ) ∗ ( n − 1 ) / n + 1 f_0=(n-1)*(n-1)/n+1 f0=(n−1)∗(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 n\%3==0 n%3==0,答案就是 2 n 2^n 2n
否则就是 2 n / 3 ∗ 3 + 1 2^{n/3*3+1} 2n/3∗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 a,b,c 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-1 n−1, n n n, n + 1 n+1 n+1
而且我们发现,想要变0,只有操作1能让数变0
所以 n − 1 n-1 n−1的情况是:有一个数为其他所有数的公因数
且只有这么一种情况。
n n n的情况比较多:
1、能找出一个 x = a i % a j x=a_i\%a_j x=ai%aj,使x为其他所有数的因数
2、能找出一个数x,使得 a i + x a_i+x ai+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
*/