并不智能的卡牌 AI
特判二者都等于0的时候
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main()
{
int m, n;
cin >> m >> n;
if(m == 0 && n == 0) cout << 0 << endl;
else if(!n) cout << -1 << endl;
else cout << ceil(double(m * 1.0 / n) )<< endl;
return 0;
}
古老的恩尼格玛机
水题，map映射一下
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
map<char, char> mp;
string s;
int main()
{
char a, b;
for(int i=1; i<=13; i++)
{
cin >>a >> b;
mp[a]= b;
mp[b] = a;
}
int k;
cin >> k;
for(int i=1; i<=k; i++)
{
cin >> s;
for(int j=0; j<s.size(); j++)
{
cout << mp[s[j]];
}
cout << " ";
}
}
差不多得了
水题
找出来1的个数，如果1是连续的就合并成一个
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int a[35];
int main()
{
int t;
cin >> t;
while(t--)
{
int n; cin >> n;
int cnt =0;
for(int i=1; i<=n; i++)
{
cin >> a[i];
if(a[i] == 1 && a[i-1] != 1) cnt ++;
}
cout << cnt << endl;
}
}
如何才能穿过传送门
水题
小模拟
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
#define endl '\n'
map<int, int> wall, door;
int main()
{
int n, m, q;
cin >> n >> m >> q;
int x, y;
for(int i=1; i<=m; i++)
{
cin >> x >> y;
door[x] = y;
}
for(int i=1; i<=q; i++)
{
cin >> x;
wall[x] = 1;
}
for(int i=1; i<=n; i++)
{
if(door.count(i))
{
i = door[i] - 1;
continue;
}
if(wall.count(i))
{
puts("NO");
return 0;
}
}
puts("YES");
return 0;
}
多吃蘑菇
由于每个点只能经过一次，所以到子节点的路径一开始就确定了，要用dfs
就是从头往下走，如果这个颜色没吃过，而且这个点没走过，就把它加进来，如果这个颜色之前走过，就比较一下，哪个大要哪个，这个不用特判之前走没走过，只要一直搜，不走回头路，总是第一次搜到
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
#define endl '\n'
#define int long long
int co[N], w[N];
vector<int> tr[N];
bool st[N];
int res[N];
multiset<int> s[N + 5];
int ans, a, b;
void dfs(int u, int pre)
{
int k = 0;
if(s[co[u]].empty()) ans += w[u], k = w[u];
else if(-*s[co[u]].begin() < w[u]) ans -= -*s[co[u]].begin(), ans += w[u], k = *s[co[u]].begin() + w[u];
s[co[u]].insert(-w[u]);
res[u] = ans;
for(auto i : tr[u])
{
if(i != pre)
{
dfs(i, u);
}
}
s[co[u]].erase(s[co[u]].find(-w[u]));
ans -= k;
}
signed main()
{
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> w[i];
for(int i=1; i<=n; i++) cin >> co[i];
for(int i=1; i<=n - 1; i++)
{
cin >> a >> b;
tr[a].push_back(b);
tr[b].push_back(a);
}
dfs(1, -1);
for(int i=1; i<=n; i++) cout << res[i] << endl;
return 0;
}
数学题真难啊
虽然忘记了叫什么dp，但是就是个dp
根据i是奇数还是偶数，来判断是加在j上还是k上
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 3e5 + 10, mod = 998244353;
int f[N][4][10];
int main()
{
f[0][0][0] = 1;
int n;
cin >> n;
for(int i=1; i<=n; i++)
{
for(int j=0; j<=2; j++)
{
for(int k = 0; k<=8; k++)
{
for(int l=0; l<=9; l++)
{
if(i&1)
{
f[i][(j + l) % 3][k] += f[i-1][j][k];
f[i][(j + l) % 3][k] %= mod;
}
else
{
f[i][j][(k + l) % 9] += f[i-1][j][k];
f[i][j][(k + l) % 9] %= mod;
}
}
}
}
}
cout << f[n][0][0] << endl;
return 0;
}
逃离魔爪
这道题的异或跟加法一样，所以就是直接上板子
二维树状数组模板题
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define LL long long
using namespace std;
const int maxa=1024*2+10;//~~pow(2,11)+10
LL n,m;
LL C1[maxa][maxa],C2[maxa][maxa],C3[maxa][maxa],C4[maxa][maxa];//开辟四个树状数组用于维护
LL lowbit(LL i){
return i&-i;
}
void add(LL a,LL b,LL k){
for(LL i=a;i<=n;i+=lowbit(i))
for(LL j=b;j<=m;j+=lowbit(j)){
C1[i][j]+=k;
C2[i][j]+=k*a;
C3[i][j]+=k*b;
C4[i][j]+=k*a*b;
}
}
LL sum(LL x,LL y){
LL ans=0;
for(LL i=x;i>0;i-=lowbit(i))
for(LL j=y;j>0;j-=lowbit(j))
ans+=(x+1)*(y+1)*C1[i][j]-(y+1)*C2[i][j]-(x+1)*C3[i][j]+C4[i][j];
return ans;
}
int main(){
scanf("%lld%lld",&n,&m);
LL op,a,b,c,d,k;
while(scanf("%lld",&op)!=EOF){
if(op==1){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
k = 1;
add(a,b,k);
add(c+1,d+1,k);
add(c+1,b,-k);
add(a,d+1,-k);
//一维差分数组应该为：add(x,k),add(y+1,-k);
}
else if(op==2){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
int res = sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1);
if(res & 1) puts("1");//对于区间更新的查询
else puts("0");
}
}
return 0;
}
到底是多少分啊
前缀和dp
首先说一下，期望呢就是，总分/方案数，方案数怎么求呢，这里的方案数就是相当于，有t个小球，要放在n个盒子里面，小球都是一样的，但是盒子是不一样的，求所有的方案数
以上就是方案数的数量，接下来，乘积的推导，可看这个
题解
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int M = (int)3e3;
const int N = (int)1e5;
const int mod = (int)998244353;
int n, t;
int a[M + 5];
int f[M + 5][M + 5];
int sum[M + 5][M + 5];
int fac[M * 2 + 5];
int inv[M * 2 + 5];
int invfac[M * 2 + 5];
void init()
{
fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;
for(int i = 2; i <= 2 * M; ++i)
{
fac[i] = (ll)fac[i - 1] * i % mod;
inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
invfac[i] = (ll)invfac[i - 1] * inv[i] % mod;
}
}
int C(int n, int m) {
if(n < 0 || m < 0 || n < m) return 0;
return (ll)fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
int quick(int a, int b, int p = mod) {
int s = 1;
while(b) {
if(b & 1) s = (ll)s * a % p;
a = (ll)a * a % p;
b >>= 1;
}
return s % p;
}
int Inv(int n, int p = mod) {
return quick(n, p - 2, p);
}
void work()
{
init();
scanf("%d%d", &n, &t);
f[0][0] = 1;
for(int i = 0; i <= t; ++i) sum[0][i] = 1;
for(int i = 1, a; i <= n; ++i)
{
scanf("%d", &a);
f[i][0] = (ll)f[i - 1][0] * a % mod;
sum[i][0] = f[i][0];
for(int j = 1; j <= t; ++j)
{
f[i][j] = (f[i][j - 1] + (ll)f[i - 1][j] * a + sum[i - 1][j - 1]) % mod;
sum[i][j] = (sum[i][j - 1] + f[i][j]) % mod;
}
}
int ans = (ll)f[n][t] * Inv(C(n + t - 1, t)) % mod;
printf("%d\n", ans);
}
int main() {
int T = 1;
for(int tt = 1; tt <= T; ++tt)
work();
return 0;
}
