Problems: 给你长度为N的，只含‘A’,'D'的序列，统计并输出何者出现的较多，相同为"Friendship"
Analysis:
lucky_ji: 水题，模拟统计A和D的数目比较大小输出结果即可
Tags: Implementation
Problems: 给定k2个2，k3个3，k5个5及k6个6，可以组成若干个32或256，求所有方案中Sigma的最大值
Analysis:
lucky_ji: 同样是水题 贪心先构造256，再构造32就行 一个式子出结果 Ans=min({k2,k5,k6})*256+min(k2-min({k2,k5,k6}),k3)*32
Tags: Greedy
Problems: 给定n个单位，每个单位花费为x，同时给定初始魔法值s，有两种咒语，每种至多使用一个，第一类有m个，消耗d_i,可以让所有单位花费变为a_i,第二类有k个，消耗d_i, 可以让c_i个单位花费变为0，求最小总花费。输入保证c_i, d_i单调递增
Analysis:
lucky_ji: 2类药剂代价和效果输入均满足不递减，故可以用二分搜索 首先先把单用一种药剂的最小代价求出，对于每一种1类药剂，其代价为X，总可用代价为V，二分查找组合使用的效果最好的2类药剂，查找条件是所有代价Y满足X+Y<V的药剂中，在输入序列中最靠后的。枚举1类药剂，找出用两瓶药剂能得到的最小价值，取两个最小价值中较小的那个。若一瓶药剂都不能使用，输出没使用药剂的代价。
P.s. 注意数据规模，int越界。
Tags: Dynamic Programming, Binary search, Greedy
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<fstream>
#include<math.h>
#include<map>
#include<queue>
#include <iomanip>
#include<stdio.h>
using namespace std;
const double PI=acos(-1.0);
const double eps=1e-;
#define Max(a,b) (a)>(b)?(a):(b)
#define Min(a,b) (a)<(b)?(a):(b)
long long n,m,k,x,s,a[][],b[][],now;
long long ans,qwe;
long fi(long x){
long s,t,now;
if (b[][]>x)
return -;
s=;
t=k;
now=(s+t)/;
while (!((s==t)||(b[now-][]==x)||((s+)==t))){
if (b[now-][]>x){
t=now;
now=(s+t)/;
}
else{
s=now;
now=(s+t)/;
}
}
while (((now+)<=k)&&(b[now][]<=x)){
now++;
}
return now-;
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&k,&x,&s);
ans=n*x;
for (int i=;i<m;i++){
scanf("%d",&a[i][]);
}
for (int i=;i<m;i++){
scanf("%d",&a[i][]);
if (a[i][]<=s)
ans=Min(ans,n*(a[i][]));
}
for (int i=;i<k;i++){
scanf("%d",&b[i][]);
}
for (int i=;i<k;i++){
scanf("%d",&b[i][]);
if (b[i][]<=s)
ans=Min(ans,(n-b[i][])*x);
}
for (int i=;i<m;i++){
qwe=s-a[i][];
now=fi(qwe);
if (now!=-)
ans=Min(ans,(n-b[now][])*(a[i][]));
}
printf("%lld\n",ans);
return ;
}
Code by lucky_ji
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF (1ll<<62)
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 200010
typedef long long ll; int n, m, k, x, s;
int a[Maxn], b[Maxn], c[Maxn], d[Maxn]; inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-; while ((ch=G_c()) && (!Dig(ch))); } x=ch-; while ((ch=G_c()) && (Dig(ch))) x=x*+ch-; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; } inline int Find(int x)
{
int l=, r=k;
while (l<=r)
{
int mid=(l+r)>>;
if (d[mid]<=x) l=mid+; else r=mid-;
}
return l;
} int main()
{
read(n); read(m); read(k); read(a[]); read(s);
for (int i=; i<=m; i++) read(a[i]);
for (int i=; i<=m; i++) read(b[i]);
for (int i=; i<=k; i++) read(c[i]);
for (int i=; i<=k; i++) read(d[i]);
ll Res=INF;
for (int i=; i<=m; i++)
if (s-b[i]>=)
{
int Cur=Find(s-b[i]);
Res=min(Res, (ll)a[i]*(n-c[Cur-]));
}
printf("%lld\n", (Res==INF)?(-):(Res));
}
Code by Return
#define PRON "734c"
#include <cstdio>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll; const int MAXN = + ; ll ans;
int n, m, k, x, s, a[MAXN], b[MAXN], c[MAXN], d[MAXN]; int main(){
#ifndef ONLINE_JUDGE
freopen(PRON ".in", "r", stdin);
#endif cin >> n >> m >> k >> x >> s;
for (int i = ; i < m; i ++)
scanf("%d", a + i);
for (int i = ; i < m; i ++)
scanf("%d", b + i);
for (int i = ; i < k; i ++)
scanf("%d", c + i);
for (int i = ; i < k; i ++)
scanf("%d", d + i); ans = ((ll)n - c[upper_bound(d, d + k, s) - d - ]) * (ll)x;
for (int i = ; i < m; i ++)
if (b[i] <= s){
int p = upper_bound(d, d + k, s - b[i]) - d - ;
ans = min(ans, (ll)(n - c[p]) * (ll)a[i]);
} cout << ans << endl;
}
Code by cj
Problems: 在国际象棋规则背景下，给定King的初始位置，和n个棋子的位置，其中棋子有Bishop，Rook和Queen三种，问是否可以移动某一个棋子使得在一步之内使游戏结束（结束条件为国王死亡）
Analysis:
lucky_ji:简单的模拟题，不难，注意细节就行。存储8个方向（上、下、左、右、左上、左下、右上、右下）上离国王最近的棋子，判断是否被将死即可。
cj:我原来喜欢用的const int inf = ox3f3f3f3f小了
Tags: Implementation
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2100000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Pend ((ch=='R') || (ch=='Q'))
typedef long long ll; int n, x0, _y0, x, y, l, r, u, d, Opt_l, Opt_r, Opt_u, Opt_d, Jge[][], Opt[][];
char ch; inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-; while ((ch=G_c()) && (!Dig(ch))); } x=ch-; while ((ch=G_c()) && (Dig(ch))) x=x*+ch-; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; } int main()
{
scanf("%d", &n);
read(x0); read(_y0);
l=r=u=d=Jge[][]=Jge[][]=Jge[][]=Jge[][]=INF;
for (int i=; i<=n; i++)
{
ch=G_c(); while ((ch^'R') && (ch^'Q') && (ch^'B')) ch=G_c();
read(x); read(y); int Lim_y=abs(_y0-y), Lim_x=abs(x0-x);
if (x==x0)
{
if (y<_y0)
if (l>=_y0-y) l=Lim_y, Opt_l=Pend; else;
else
if (r>=y-_y0) r=Lim_y, Opt_r=Pend; else;
}
else
if (y==_y0)
{
if (x<x0)
if (u>=x0-x) u=Lim_x, Opt_u=Pend; else;
else
if (d>=x-x0) d=Lim_x, Opt_d=Pend; else;
}
else
if ((Lim_x==Lim_y) && (Jge[x>x0][y>_y0]>Lim_x))
{
Jge[x>x0][y>_y0]=Lim_x;
Opt[x>x0][y>_y0]=((ch=='B') || (ch=='Q'));
}
}
bool flag=((Opt_l) || (Opt_r) || (Opt_u) || (Opt_d) || (Opt[][]) || (Opt[][]) || (Opt[][]) || (Opt[][]));
puts(flag?"YES":"NO");
}
Code by Return
#define PRON "734d"
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll; const int inf = + ;
const int maxn = + ; char t;
pair<int, int> b[][], r[][];
int n, x, y, _x, _y, sb[][], sr[][]; int sig(int now){
if (now < )
return ;
if (now > )
return ;
return ;
} bool check(){
for (int i = ; i < ; i ++)
for (int j = ; j < ; j ++)
b[i][j] = r[i][j] = make_pair(inf, inf); int _t;
for (int i = ; i < n; i ++){
cin >> t >> _x >> _y;
_x -= x, _y -= y;
if (t == 'B')
_t = ;
else if (t == 'R')
_t = ;
else
_t = ; if (abs(_x) == abs(_y) && abs(_x) < abs(b[sig(_x)][sig(_y)].first))
b[sig(_x)][sig(_y)] = make_pair(_x, _y), sb[sig(_x)][sig(_y)] = _t; if (_x == && abs(_y) < abs(r[sig(_x)][sig(_y)].second))
r[sig(_x)][sig(_y)] = make_pair(_x, _y), sr[sig(_x)][sig(_y)] = _t; if (_y == && abs(_x) < abs(r[sig(_x)][sig(_y)].first))
r[sig(_x)][sig(_y)] = make_pair(_x, _y), sr[sig(_x)][sig(_y)] = _t;
} for (int i = ; i < ; i ++)
for (int j = ; j < ; j ++)
if ((b[i][j].first != inf && sb[i][j] != ) || (r[i][j].first != inf && sr[i][j] != ))
return true; return false;
} int main(){
#ifndef ONLINE_JUDGE
freopen(PRON ".in", "r", stdin);
#endif cin >> n >> x >> y; puts(check() ? "YES" : "NO");
}
Code by cj
Problems: 给定一个有n个点的树，树上点有黑白两色，每次可以执行paint操作，该操作可以使和这个点相连的所有同色点颜色取反，且代价为1，问最小代价
Analysis:
lucky_ji: 稍有点难度，首先DFS把相同颜色的点缩为一个点，得到一个树，问题变为每次可以对得到的树中的一个节点进行一次操作，操作会使一个节点将周围的点吞掉并合并为一个节点。目标是使树只剩一个点。那么问题就变成了最少经过几次操作后能使树的直径为1，答案显然为树的直径div 2，每次都是对直径的中点进行操作，所以在缩点后只要进行两次BFS求出直径，再div2即为答案。
Return: 考虑到lucky_ji解答中的的缩点再搜索，其实对比两颗树可以发现，新树的直径可以通过在dfs维护dep得到，而显然，只有该节点颜色和其父节点不同时，才考虑dep+1，从而有效减少了代码量
Tags: Dfs and Similar, Trees
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<fstream>
#include<math.h>
#include<map>
#include<queue>
#include <iomanip>
#include<stdio.h>
using namespace std;
const double PI=acos(-1.0);
const double eps=1e-;
#define Max(a,b) (a)>(b)?(a):(b)
#define Min(a,b) (a)<(b)?(a):(b)
int s[],t[],n[],st[],num,nn,a[],F[],b,s0[],t0[],n0[],st0[],d[],ans;
bool f[],ff[];
void dfs(int now){
f[now]=false;
F[now]=num;
int q=st[now];
while (q!=-){
if ((f[t[q]])&&(a[now]==a[t[q]])){
dfs(t[q]);
}
q=n[q];
}
}
void dfs0(int now){
f[now]=false;
int q=st[now];
while (q!=-){
if ((f[t[q]])&&(a[now]==a[t[q]])){
dfs0(t[q]);
}
else{
b++;
s0[b]=F[now];
t0[b]=F[t[q]];
n0[b]=st0[F[now]];
st0[F[now]]=b;
}
q=n[q];
}
}
void bfs(){
int q,now,tot,sos,ttt;
d[]=;
tot=;
sos=;
while (sos<=tot){
ttt=tot;
for (int i=sos;i<=tot;i++){
now=d[i];
ff[now]=false;
q=st0[now];
while (q!=-){
if (ff[t0[q]]){
ttt++;
d[ttt]=t0[q];
}
q=n0[q];
}
}
sos=tot+;
tot=ttt;
}
d[]=d[ttt];
tot=;
sos=;
ans=;
while (sos<=tot){
ans++;
ttt=tot;
for (int i=sos;i<=tot;i++){
now=d[i];
ff[now]=true;
q=st0[now];
while (q!=-){
if (!ff[t0[q]]){
ttt++;
d[ttt]=t0[q];
}
q=n0[q];
}
}
sos=tot+;
tot=ttt;
}
}
int main(){
scanf("%d",&nn);
for (int i=;i<=nn;i++){
scanf("%d",&a[i]);
f[i]=true;
st[i]=-;
}
for (int i=;i<nn;i++){
scanf("%d%d",&s[i*-],&t[i*-]);
s[i*]=t[i*-];
t[i*]=s[i*-];
n[i*-]=st[s[i*-]];
st[s[i*-]]=i*-;
n[i*]=st[s[i*]];
st[s[i*]]=i*;
}
num=;
for (int i=;i<=nn;i++){
if (f[i]){
num++;
dfs(i);
}
}
for (int i=;i<=num;i++){
ff[i]=true;
st0[i]=-;
b=;
}
for (int i=;i<=nn;i++){
if (!f[i]){
dfs0(i);
}
}
bfs();
printf("%d\n",ans/);
}
Code by lucky_ji
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxe 400010
#define Maxn 200010
typedef long long ll; int n, Col[Maxn], From, Diameter, x, y;
int To[Maxe], Next[Maxe], Head[Maxe], Cnt; inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-; while ((ch=G_c()) && (!Dig(ch))); } x=ch-; while ((ch=G_c()) && (Dig(ch))) x=x*+ch-; x*=N; }
inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; } inline void dfs(int u, int father, int depth)
{
if (depth>Diameter) From=u, Diameter=depth;
for (int p=Head[u]; p!=-; p=Next[p])
{
int v=To[p];
if (v^father) dfs(v, u, depth+(Col[u]^Col[v]));
}
} int main()
{
Cnt=; Clear(Head, -);
read(n);
for (int i=; i<=n; i++) read(Col[i]);
for (int i=; i<n; i++) read(x), read(y), Insert(x, y), Insert(y, x);
dfs(, -, ); Diameter=-; dfs(From, -, );
printf("%d\n", Diameter>>);
}
Code by Return
Problems:构造序列a，满足如下性质，判断其是否合法并输出a
Analysis:
Return: 稍作观察即可发现b_i+c_i=a_i*n+a_1+a_2+..+a_n，令其为d_i, 从而可以求解出a_i=(d_i-(d_1+d_2+..+d_n)/(2*n))/n
之后就是判断a_i是否合法了，不合法只有两种情况：1.a_i<0 2.由a_i反解出的b_i和c_i和原b_i和c_i不对应。
对于后者，显然常规n^2构造会Time Limit Exceed，这时候回归题目，发现对于a_i在二进制下的第j位，可以统计该位在a_1..a_n*有几个1，记为Sig_j，则b_i的计算为：当a_i第j位不为0时，由于对于该位来说，a_i执行&操作只有对a_1..a_n中该位同样为1的数有效，从而b_i=(Sig_j<<j)，而a_i为0时，无论其他a在该位取何值，对该位的贡献仍然为0，同样可以推出c_i为(n<<j)//a_i第j位不为0，(Sig_j<<j)//a_i第j位为0，从而复杂度为O(nlog(Max_a_i_length))
Tags: Bitmasks, Math, Implementation
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 200010
typedef long long ll; int n, b[Maxn], c[Maxn];
ll _b, _c, d[Maxn], a[Maxn], Sig, bit[Maxn][], Sig_bit[], Max; inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-; while ((ch=G_c()) && (!Dig(ch))); } x=ch-; while ((ch=G_c()) && (Dig(ch))) x=x*+ch-; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; } int main()
{
read(n);
for (int i=; i<=n; i++) read(b[i]);
for (int i=; i<=n; i++)
{
read(c[i]);
d[i]=(ll)b[i]+c[i], Sig+=d[i];
}
Sig/=(n<<);
for (int i=; i<=n; i++)
{
a[i]=(d[i]-Sig)/n;
if (a[i]<) { puts("-1"); return ; }
Max=max(Max, a[i]);
}
int Limit=(int)log2(Max); if ((1ll<<Limit)<Max) Limit++;
for (int i=; i<=n; i++)
for (int j=; j<=Limit; j++)
bit[i][j]=(a[i]&(1ll<<j)), Sig_bit[j]+=((bit[i][j])?():());
for (int i=; i<=n; i++)
{
_b=_c=;
for (int j=; j<=Limit; j++)
{
ll Cur=(Sig_bit[j]<<j);
if (bit[i][j]) _b+=Cur, _c+=((ll)n<<j); else _c+=Cur;
}
if ((_b^b[i]) || (_c^c[i])) { puts("-1"); return ; }
}
for (int i=; i<n; i++) printf("%lld ", a[i]); printf("%lld\n", a[n]);
}
Code by Return