#include <bits/stdc++.h>
using i64 = long long;
const int N = 5100;
int f[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> v(n + 1,0);
memset(f,0x3f,sizeof f);
int m = n;
f[0] = 0;
for (int i = 1; i <= n; i ++)
{
int x;
std::cin >> x;
for (int j = i; j <= m; j ++ )
f[j] = std::min(f[j],f[j - i] + x);
}
std::cout << f[n] << "\n";
return 0;
}
#include <bits/stdc++.h>
using i64 = long long;
int n;
void solve()
{
int ans = 0;
std::vector<int> a(n);
for (int i = 0; i < n; i ++ )
{
std::cin >> a[i];
ans ^= a[i];
}
if(!ans)
{
std::cout << "0\n";
return;
}
int res = 0;
for (int i = 0; i < n; i ++)
{
int k = ans ^ a[i];
res += (a[i] > k);
}
std::cout << res << "\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
while(std::cin >> n and n) {
solve();
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
using i64 = long long;
const int N = 1100;
int f[N][N];
int n,m;
std::string a,b;
void solve()
{
memset(f,0,sizeof f);
a = " " + a,b = " " + b;
for (int i = 0; i <= m; i ++) f[0][i] = i;
for (int i = 0; i <= n; i ++) f[i][0] = i;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
f[i][j] = std::min(f[i - 1][j],f[i][j - 1]) + 1;
f[i][j] = std::min(f[i][j],a[i] == b[j] ? f[i - 1][j - 1] : f[i - 1][j - 1] + 1);
}
std::cout << f[n][m] << "\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
while(std::cin >> n >> a >> m >> b) {
solve();
}
return 0;
}
#include <bits/stdc++.h>
using i64 = long long;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n,m;
while(std::cin >> n >> m and (n or m))
{
if (n > m) std::swap(n,m);
int k = m - n;
int t = (1 + std::sqrt(5.0)) / 2 * k;
if (t == n) std::cout << "0\n";
else {
std::cout << "1\n" << t << " " << m - n + t << "\n";
int s = (std::sqrt(5.0) - 1) / 2 * n;
std::cout << s << " " << n << "\n";
}
}
return 0;
}
快速幂求逆元
#include <bits/stdc++.h>
using i64 = long long;
const i64 mod = 9973;
//a^b%p
template<class T>
T qmi(T a, i64 b,T p) {
int res = 1 % p;
while (b)
{
if (b & 1) res = (i64)res * a % p;
a = a * (i64)a % p;
b >>= 1;
}
return res;
}
void solve()
{
i64 a,b;
std::cin >> a >> b;
i64 t = qmi(b,mod - 2,mod);
std::cout << a * t % mod << "\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
std::cin >> T;
while(T -- ){
solve();
}
return 0;
}
扩展欧几里得求逆元
#include <bits/stdc++.h>
using i64 = long long;
const i64 mod = 9973;
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y -= (a/b)*x;
return d;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while(t--)
{
int n,b,x,y;
std::cin >> n >> b;
int d = exgcd(b,mod,x,y);
x = ((x % mod)+mod) % mod;
std::cout << ((x * n) % mod ) % mod << "\n";
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 32010;
int n;
int res[N];
////区间修改,单点查询
int c[N];//c[x]表示a[x - lowbit(x) + 1,x] 之间所有数的和
struct BT
{
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int v)
{
for(int i = x; i <= N; i += lowbit(i))
c[i] += v;
}
int query(int x)
{
int ans = 0;
for(int i = x; i; i -= lowbit(i)) ans += c[i];
return ans;
}
}BTree;
int main()
{
std::cin >> n;
for(int i = 1; i <= n; i ++ )
{
int x,y;
std::cin >> x >> y;
x ++;
res[BTree.query(x)]++;
BTree.add(x,1);
}
for(int i = 0; i < n; i ++ )
std::cout << res[i] << "\n";
return 0;
}
#include <bits/stdc++.h>
using i64 = long long;
const int N = 110;
int g[N][N];
int n;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int a,b,k = 1;
while(std::cin >> a >> b,(a or b))
{
memset(g,0x3f,sizeof g);
g[a][b] = 1;
int n = 0;
while(1)
{
std::cin >> a >> b;
n = std::max(n,std::max(a,b));
g[a][b] = 1;
if(a == 0 and b == 0) break;
}
for (int i = 0; i <= n; i ++) g[i][i] = 0;
auto floyd = [&](){
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
g[i][j] = std::min(g[i][j],g[i][k] + g[k][j]);
};
floyd();
int sum = 0;
int cnt = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if(g[i][j] != 0x3f3f3f3f and g[i][j] > 0)
{
sum += g[i][j];
cnt ++;
}
std::cout << "Case " << k << ": average length between pages = "<< std::fixed << std::setprecision(3) << (double)sum / cnt << " clicks\n";
k ++;
}
return 0;
}
#include <bits/stdc++.h>
using i64 = long long;
const int N = 2e5+10;
int w[N];
struct node
{
int l,r;
int v;//区间[l,r]中的最大值,或自身的值
}tree[N*4];
int n,m;
struct Segment_Tree
{
void build_tree(int u,int l,int r)
{
tree[u].l = l,tree[u].r = r;
if(l == r)
{
tree[u].v = w[l];
return;
}
int mid = l + r >> 1;
build_tree(u << 1,l,mid), build_tree(u << 1 | 1,mid + 1,r);
pushup(u);
}
void pushup(int u)//由子节点的信息,来更新父节点的信息
{
tree[u].v = std::max(tree[u << 1].v,tree[u << 1 | 1].v);
}
int query(int u,int l,int r)
{
if(tree[u].l >= l and tree[u].r <= r) return tree[u].v;//树中界定已经全部包含在[l,r]中
int mid = tree[u].l + tree[u].r >> 1;
int v = 0;
if(l <= mid) v = query(u << 1,l,r);
if(r > mid) v = std::max(v,query(u << 1 | 1,l,r));
return v;
}
void modify(int u,int x,int v)
{
if(tree[u].l == x and tree[u].r == x) tree[u].v = v;
else
{
int mid = tree[u].l + tree[u].r >> 1;
if(x <= mid) modify(u << 1,x,v);
else modify(u << 1 | 1,x,v);
pushup(u);
}
}
}ST;
void solve()
{
for (int i = 1; i <= n; i ++) std::cin >> w[i];
ST.build_tree(1,1,n);
while(m -- )
{
std::string s;
int l,r;
std::cin >> s >> l >> r;
if(s == "Q") {
std::cout << ST.query(1,l,r) << "\n";
} else {
ST.modify(1,l,r);
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
while(std::cin >> n >> m)
{
solve();
}
return 0;
}
#include <bits/stdc++.h>
using i64 = long long;
//通解:x = x0 + k*(b/d) y = y0 + k*(a/d)
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x = 1,y = 0;
return a;
}
int d = exgcd(b,a%b,y,x);
y -= a / b * x;
return d;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int a,b;
std::cin >> a >> b;
int x,y;
exgcd(a,b,x,y);
std::cout << (x % b + b) % b << "\n";
return 0;
}