闲话
感觉这场最难的就是D,到现在都不太理解
A - Very Very Primitive Game
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
int main()
{
int a,b,c;cin >> a >> b >> c;
while(1)
{
if(c == 0)
{
if(a == 0) return cout << "Aoki",0;
--a;
}
else
{
if(b == 0) return cout << "Takahashi",0;
--b;
}
c ^= 1;
}
return 0;
}
B - Magic 3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n,s,d;cin >> n >> s >> d;
forn(i,1,n)
{
int x,y;cin >> x >> y;
if(x < s && y > d) return cout << "Yes",0;
}
cout << "No";
return 0;
}
C - Bowls and Dishes
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
typedef pair<int,int> pii;
#define x first
#define y second
const int N = 105;
pii need[N],p[N];
bool st[N];
int main()
{
int n,m;scanf("%d%d",&n,&m);
forn(i,1,m) scanf("%d%d",&need[i].x,&need[i].y);
int k;scanf("%d",&k);
forn(i,1,k) scanf("%d%d",&p[i].x,&p[i].y);
int res = 0;
forn(S,0,(1 << k) - 1)
{
forn(i,1,n) st[i] = 0;
forn(j,0,k - 1)
{
if(S >> j & 1) st[p[j + 1].x] = 1;
else st[p[j + 1].y] = 1;
}
int tmp = 0;
forn(i,1,m) if(st[need[i].x] && st[need[i].y]) ++tmp;
res = max(res,tmp);
}
printf("%d",res);
return 0;
}
D - Staircase Sequences
题目大意:给定一个\(n\)求公差为\(1\)的等差数列且和为\(n\)的方案数.
数据范围:\(1 \leq N \leq 10^{12}\)
思路
设这个等差数列首项为\(x\)末项为\(y\)则有\((x+y)*(y - x + 1) = 2 * N\).那么根据复杂度反推,可能是个根号算法,可以分解\(2*N\)的约数\(d\),那么枚举\(d\)的同时\(N/d\)也是一个合法的约数,此时有两种情况:要么\(d=(x+y)\)此时可以反推出一个条件,要么\(d=(y-x+1)\)此时也可以反推出一个条件,根据条件判断当前情况是否合法,如果合法就累加.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
int main()
{
ll N;cin >> N;
ll n = 2 * N;
ll res = 0;
for(ll i = 1;i <= n / i;++i)
{
if(n % i == 0)
{
// cout << i << " " << n / i << endl;
ll d = i;
if((d * d + d - n) % (2 * d) == 0) ++res;
if((n - d * d + d) % (2 * d) == 0) ++res;
}
}
cout << res << endl;
return 0;
}
E - Magical Ornament
题目大意:有\(n\)个石头,编号从\(1\)开始,有\(m\)对关系表示一对石头可以摆放在相邻的位置,如果两个石头没有这样的关系则不可以放在相邻的位置.现在要做一个牛逼的法阵,这个法阵是一排连续的石头,要求相邻的石头满足关系,并且整个序列需要包含指定的\(k\)个牛逼石头,其编号由\(c_1,c_2...c_k\)指定.求一个合法的牛逼法阵最少需要多少个石头.
数据范围:
\(1 \leq n,m \leq 10^5\)
\(1 \leq k \leq 17\)
思路
思路肯定从特别小的\(k\)入手,因为要包含指定的\(k\)个牛逼石头,所以很自然的可以想到拿状压记录每个牛逼石头的选取状态.可以初步地把状态转移方程搞出来:
- 状态:\(f[S][i]\)表示当前选取的石头集合是\(S\),最后一个选取的牛逼石头是\(i\).
- 入口:\(f[1 << i][i] = 1\)只选取一个石头自己的时候
- 转移:枚举当前\(S\)中存在的一个石头\(j\)并且枚举将要加入这个集合的下一个石头\(i\),那么首先需要满足这两个变量与集合的关系,其次转移就是\(f[S | (1 <<i)][i] = min(f[S | (1 << i)][i],f[S][j] + dist(j,C[i]))\).因为这里有个问题:这个石头\(j\)他不一定是和下一个\(i\)可以直接相邻摆放的,但是并不意味着就不能放入\(i\)了,可以在\(j\)之后放入一些石头并且最终联通向\(i\),所以这里的\(dist(j,i)\)就表示从一个牛逼石头\(j\)连向任意一个石头\(i\)的距离(当然转移方程里面是指定的牛逼石头\(C_i\)才对).
- 出口:\(\min\limits_{i=1}^n{f[S][i]}\).
- 注意实际写代码的时候有所有编号调整到从\(0\)开始的操作.
现在的问题就是剩下一个\(dist\)的处理了,建图比较简单,如果两个石头之间存在可相邻关系那么就连一条权值为\(1\)的无向边.同时也不需要求任意两点的距离,牛逼石头最多\(17\)个,所以预处理出来每个牛逼石头的单源最短路就可以了.因为权值都是\(1\)所以跑个简单的BFS就可以了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 1e5+7,M = 2 * N,CK = 20,INF = 0x3f3f3f3f;
int dist[CK][N],c[CK];
int edge[M],succ[M],ver[N],idx;
int f[1 << 17][CK];
void add(int u,int v)
{
edge[idx] = v;
succ[idx] = ver[u];
ver[u] = idx++;
}
void bfs(int f)
{
memset(dist[f],0x3f,sizeof dist[f]);
queue<int> q;q.push(c[f]);dist[f][c[f]] = 0;
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(dist[f][v] > dist[f][u] + 1)
{
dist[f][v] = dist[f][u] + 1;
q.push(v);
}
}
}
}
int main()
{
memset(ver,-1,sizeof ver);
int n,m;scanf("%d%d",&n,&m);
forn(i,1,m)
{
int u,v;scanf("%d%d",&u,&v);
--u;--v;
add(u,v),add(v,u);
}
int k;scanf("%d",&k);
forn(i,0,k - 1) scanf("%d",&c[i]),--c[i];
forn(i,0,k - 1) bfs(i);
memset(f,0x3f,sizeof f);
forn(i,0,k - 1) f[1 << i][i] = 1;
forn(S,1,(1 << k) - 1)
{
forn(j,0,k - 1) forn(i,0,k - 1)
{
if(f[S][j] == INF) continue;
if(!(S >> j & 1) || dist[j][c[i]] == INF || (S >> i & 1)) continue;
f[S | (1 << i)][i] = min(f[S | (1 << i)][i],f[S][j] + dist[j][c[i]]);
}
}
int res = INF;
forn(i,0,k - 1) res = min(res,f[(1 << k) - 1][i]);
printf("%d",res == INF ? -1 : res);
return 0;
}
F - Shift and Inversions
思路
因为每次修改都是把第一个元素放到最后一个元素,所以直接树状数组维护一下值域查询就可以了.
逆序对是\(n^2\)级别的,需要开ll.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 3e5+7;
int c[N],a[N];
int n;
inline int lowbit(int x)
{
return x & -x;
}
void modify(int x,int v)
{
for(int i = x;i < N;i += lowbit(i))
c[i] += v;
}
int query(int x)
{
int res = 0;
for(int i = x;i;i -= lowbit(i))
res += c[i];
return res;
}
int main()
{
scanf("%d",&n);
ll res = 0;
forn(i,1,n)
{
scanf("%d",&a[i]);
a[i]++;
res += query(N - 1) - query(a[i]);
modify(a[i],1);
}
printf("%lld\n",res);
forn(k,1,n - 1)
{
res -= query(a[k] - 1);
res += query(N - 1) - query(a[k]);
printf("%lld\n",res);
}
return 0;
}