Codeforces Round #558 (Div. 2)
文章目录
Codeforces Round #558 (Div. 2)
退役打cf第一场
A - Eating Soup
注意考虑全面即可
int a,b;cin>>a>>b;
if(b == 0)
cout<<1<<endl;
else if(b < (a+1)/2 )
cout<<b<<endl;
else
cout<<a-b<<endl;
B- Cat Party
分类讨论即可
num[i] 代表值为i的有多少个
ma[num[i]] 代表数量为num[i] 的有多少个
注意维护他们两个就OK了
ma的size大于等于3肯定不可以
ma的size<mark>1 ，必须是first为1,或者second为1
ma的size</mark>2，如果都是数量为1，肯定可以
如果有一个数量为1，可以直接删除
否则只能是连续的，删除数量多的那一个
const int maxn = 1e5+10;
int num[maxn];
int main(void)
{
int n;cin>>n;
int ans = 1;
map<int,int> ma;
for(int i = 1;i <= n; ++i){
int a;scanf("%d",&a);
if(num[a] != 0)
ma[num[a]]--;
if(ma[num[a]] == 0)
ma.erase(num[a]);
num[a]++;
ma[num[a]]++;
if(ma.size() >= 3) continue;
if(ma.size() ==1){
P p = *ma.begin();
if(p.second == 1) ans = i;
if(p.first == 1) ans = i;
continue;
}
if(ma.size() == 2){
auto c = ma.begin();
P p1 = *c;c++;
P p2 = *c;
if(p1.first == 1&&p1.second == 1)
ans = i;
if(p2.first == 1&&p2.second == 1)
ans = i;
if(p2.first == p1.first + 1&&p2.second == 1)
ans = i;
}
}
cout<<ans<<endl;
return 0;
}
C2 - Power Transmission (Hard Edition)
O(n2) 枚举直线，如果有和之前的重合，就舍去，如果有重合，说明至少三个点，暴力枚举第二个点即可
用pair类型存储直线的斜率有关信息，把相同斜率的存到map里面，平行的舍去，其它的相交
const int maxn = 2500*2500+10;
int x[maxn],y[maxn];
int main(void)
{
int n;cin>>n;
LL ans = 0;
map<Line,LL> ma;
map<P,int> maa;
LL num = 0;
for(int i = 1;i <= n; ++i)
{
scanf("%d%d",&x[i],&y[i]);
for(int j = 1;j < i; ++j){
Line L = Line{x[i],y[i],x[j],y[j]};
P p = P(x[i]-x[j],y[i]-y[j]);
int d = gcd(p.FI,p.SE);
p.FI /= d;
p.SE /= d;
if(p.FI < 0)
p.FI *= -1,p.SE *= -1;
bool yes = true;
for(int k = 1;k < i; ++k){
if(j == k) continue;
// Line L = Line{x[i],y[i],x[j],y[j]};
Line L2 = Line{x[j],y[j],x[k],y[k]};
// if(j == 2&&k == 1&&i == 3){
// cout<<(L == L2)<<endl;
// }
if(L == L2){
yes = false;
break;
}
}
if(!yes) continue;
ans += num-maa[p];
maa[p]++;
num++;
}
// cout<<"i = "<<i<<" "<<num<<endl;
}
// cout<<num<<endl;
cout<<ans<<endl;
return 0;
}
D - Mysterious Code
题意：给定一个c作为母串，s，t作为匹配串，其中c有一些字母不确定，定义 f(s1,s2) 为s2在s1 中出现的次数，求 max(f(c,s)−f(c,t))
分析：kmp+我为人人递推型dp，非常常见的套路
f[i][j][k]代表到了第i个字符，应该匹配s的第j个，应该匹配t的第k个，最大差是多少
现在的转态是 i,j,k 根据fail指针求出下一个 f[i+1][jj][kk]
;
const int maxn = 1000+10;
char c[maxn],s[maxn],t[maxn];
void getFail(char *P,int *f)
{
int m = strlen(P);
f[0] = 0,f[1] = 0;
for(int i = 1;i < m; ++i)
{
int j = f[i];
while(j && P[i] != P[j]) j = f[j];
f[i+1] = P[i] == P[j] ? j + 1: 0;
}
}
inline void chkmax(int &a,int b){
a = a<b?b:a;
}
const int maxm = 60;
int f[maxn][maxm][maxm];
int fs[maxm],ft[maxm];
int main(void)
{
// memset(f,-1,sizeof(f));
cin>>c>>s>>t;
int nc = strlen(c);
int ns = strlen(s);
int nt = strlen(t);
// cout<<nc<<" "<<ns<"'
getFail(s,fs);
getFail(t,ft);
for(int i = 0;i <= nc; ++i)
for(int j = 0;j<= ns; ++j)
for(int k =0;k <= nt; ++k)
f[i][j][k] = -INF;
f[0][0][0] = 0;
int ans = -INF;
for(int i = 0;i < nc;++i){
for(char ch = 'a';ch <= 'z'; ++ch){
if(c[i] !='*'&&c[i]!=ch) continue;
for(int j = 0;j <= ns; ++j){
for(int k = 0;k <= nt; ++k){
if(f[i][j][k] == -INF) continue;
int jj = j;
int kk = k;
while(jj&&ch != s[jj])jj = fs[jj];
while(kk&&ch != t[kk])kk = ft[kk];
if(ch == s[jj]) jj++;
if(ch == t[kk]) kk++;
int t= 0;
if(jj==ns)
t++;
if(kk==nt)
t--;
// cout<<t<<endl;
// int &F = f[i]
// if(t >= 1){
// cout<<i<<endl;
// }
chkmax(f[i+1][jj][kk],f[i][j][k]+t);
// f[i+1][jj][kk] = max()
}
}
}
}
for(int j = 0;j <=ns; ++j)
for(int k = 0;k <= nt; ++k)
chkmax(ans,f[nc][j][k]);
// for(int j = 0;j <= ns; ++j){
// for(int k = 0;k <= nt; ++k){
// cout<<setw(5)<<f[nc][j][k]<<" ";
// }
// cout<<endl;
// }
// getFail(ch,f);
// printf("%d",f[strlen(ch)-1]);
cout<<ans<<endl;
return 0;
}
//f[i][j][k] 代表到了第i个，s要匹配到j，t要匹配k，最大的f(i)-f(j)
/* wcfteosuhqfgokvuctvnpiiudq**ephyfyjzitxsxedsuxwlrwqwctphp*xfkfceghepmgheqazdziqjqphdtc*bryobgqzuzouoqzfcfizbiayvcryyfqsfqzwzdhmexgdmr*fvwlpuogxcpqvvzwdvhvnc*rvkllcujibmregytsyps*zvumiklue*oimvjfqshacizmdxzrupqylcjzom dxfzbdrelqidmbkgqjsobqtjqoar vbtbkqfvprnobfpbdqpomudockgjunicbu */
E - Magical Permutation
题意：给定n个数，问能构造出来的最长的 [0,2x−1] 的排列，这个排列相邻两个元素的异或都在n个数里面
分析：
重点1：因为排列中有0的存在，所以 [0,2x−1] 的所有元素都能通过s集合中的元素两两异或出来
重点2：怎么判定最大的x呢，线性基基底数如果等于x，就一定能组合成 [0,2x−1] 中的所有元素，从大到小暴力枚举x即可
重点3：怎么构造？
其实就是枚举这x个构成线性基的数的线性组合，那自然数的二进制不正好是吗？
所以我们从小到大枚举这个组合即可
const int MN=60;
const int maxn = 2e5+10;
int b[maxn];
LL a[61],tmp[61];
bool flag;
bool ins(LL x){
for(reg int i=MN;~i;i--)
if(x&(1LL<<i))
if(!a[i]){a[i]=x;return true;}
else x^=a[i];
flag=true;
return false;
}
bool check(LL x){
for(reg int i=MN;~i;i--)
if(x&(1LL<<i))
if(!a[i])return false;
else x^=a[i];
return true;
}
LL qmax(LL res=0){
for(reg int i=MN;~i;i--)
res=max(res,res^a[i]);
return res;
}
LL qmin(){
if(flag)return 0;
for(reg int i=0;i<=MN;i++)
if(a[i])return a[i];
}
LL query(LL k){
reg LL res=0;reg int cnt=0;
k-=flag;if(!k)return 0;
for(reg int i=0;i<=MN;i++){
for(int j=i-1;~j;j--)
if(a[i]&(1LL<<j))a[i]^=a[j];
if(a[i])tmp[cnt++]=a[i];
}
if(k>=(1LL<<cnt))return -1;
for(reg int i=0;i<cnt;i++)
if(k&(1LL<<i))res^=tmp[i];
return res;
}
int n;
int vec[maxn];
void check(int x){
memset(a,0,sizeof(a));
int cnt = 0;
for(int i = 1;i <= n; ++i){
if(b[i] <(1<<x)&&ins(b[i]))
vec[cnt++] = b[i];
}
if(cnt != x) return ;
// for(int i = 0;i < cnt; ++i)
// cout<<vec[i]<<endl;
int now = 0;
cout<<x<<endl;
cout<<now<<" ";
for(int i = 0;i < (1<<x); ++i){
for(int j = 0;j < x; ++j)
if((i>>j)&1)
{
now ^= vec[j];
cout<<now<<" ";
break;
}
}
exit(0);
}
int main(){
LL x;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
//,ins(x);9
for(int i = 22;i >= 0; --i)
check(i);
// printf("%lld\n",qmax());
return 0;
}
F - Indecisive Taxi Fee
CF1164F
题意
给定一个无向图，n个点，m条边及其权值，每次修改一条边的权值，询问相互独立，对于每次询问输出从1到n的最短路
分析
最短路树+线段树优化查询
1 先从1跑单源最短路dforward，在从n跑单源最短路dbackward
2 剥离出来任意一条从1到n的最短路，并对路径上的点进行编号
结论：
- 如果修改的边不再最短路上，那么最短路只有两种可能，1原来的最短路，2 经过u->v 的最短路，这两者取小即可
- 如果修改的边在最短路上
如果是减小，那么肯定还是这条路
如果是增大，那么可能还是这条路，或者不经过这条边的其它最短路
本题最重要的是求不经过某条边的最短路，怎么来求呢，我们需要知道什么是最短路树，我们从1跑单源最短路的时候就求得了最短路树，即n个点，n-1(假设都能到达)条边的树，1到每一个点的路径都是唯一的，这可以通过，每次更新的时候标记前驱节点来实现，如果一条边不在最短路上，那么他肯定与原来的最短路树形成了环，那么它就可能对这条环上的节点最短路产生贡献，我们需要对所有点进行分层，按照最短路的位置分层即每个点的层就是离他最近的最短路上的点的层数，可以通过一遍dfs来实现，一条不在最短路上的边必定连接了两个层（连接同一层是没有意义的，不会有贡献），我们建一棵线段树，将这两个层的值更新一下 dforward[u]+w+dbackward[v]
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG ;//cout<<endl<<"DEBUG"<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int prime = 999983;
const int INF = 0x7FFFFFFF;
const LL INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<LL,int> P;
const int maxn = 4e5+10;
#define ls (o<<1)
#define rs (o<<1|1)
#define int long long
LL tree[maxn<<2];
void modify(int x,int l,int r,int ql,int qr,long long v){
if(l >= ql&&r <= qr){
tree[x] = min(tree[x],v);
return;
}
int mid = (l+r)>>1;
if(ql <= mid)
modify(x<<1,l,mid,ql,qr,v);
if(qr > mid)
modify(x<<1|1,mid+1,r,ql,qr,v);
}
long long query(int x,int l,int r,int p){
if(l == r) return tree[x];
int mid = (l+r)>>1;
if(p <= mid)
return min(tree[x],query(x<<1,l,mid,p));
else
return min(tree[x],query(x<<1|1,mid+1,r,p));
}
struct Edge{
int from,to;LL w;
};
vector<Edge> edges;
vector<int> G[maxn];
void AddEdge(int u,int v,LL w){
edges.push_back(Edge{u,v,w});
edges.push_back(Edge{v,u,w});
int m = edges.size();
G[u].Pb(m-2);
G[v].Pb(m-1);
}
LL disf[maxn],disb[maxn],dis[maxn];
bool done[maxn];
int p[maxn];
void Dij(int s){
memset(dis,0x3f,sizeof(dis));
memset(done,0,sizeof(done));
memset(p,-1,sizeof(p));
dis[s] = 0;
priority_queue<P> Q;
Q.push(P(dis[s],s));
while(!Q.empty()){
int u = Q.top().second;Q.pop();
if(done[u]) continue;
done[u] = true;
for(auto id: G[u]){
int to = edges[id].to,w = edges[id].w;
if(done[to]) continue;
if(dis[to] > dis[u]+w){
dis[to] = dis[u]+w;
p[to] = id;
// cout<<to<<" "<<p[to]<<endl;
Q.push(P(-dis[to],to));
}
}
}
}
int path[maxn],id[maxn];
bool mainpath[maxn];
vector<int> E[maxn];// 抽出来的最短路树图
void dfs(int u){
for(auto v:E[u]){
if(!id[v])
id[v] = id[u];
dfs(v);
}
}
int32_t main(void){
IOS;
// cout<<(0x3f)<<endl;
memset(tree,0x3f,sizeof(tree));
int n,m,q;
cin>>n>>m>>q;
for(int i = 0;i < m; ++i){
LL u,v,w;
cin>>u>>v>>w;
AddEdge(u,v,w);
}
// 两次dij最短路
Dij(n);memcpy(disb,dis,sizeof(dis));
Dij(1);memcpy(disf,dis,sizeof(dis));
// DEBUG;
// for(int i= 1;i <= n; ++i)
// {
// cout<<i<<" "<<disf[i]<<" "<<disb[i]<<endl;
// }
// DEBUG;
// cout<<p[4]<<endl;
int len = 0;
// int i
for(int i = n;i >= 1; ){
path[++len] = i;
if(i == 1) break;
// cout<<p[i]<<endl;
assert(p[i] != -1);
mainpath[p[i]>>1] = true;
i = edges[p[i]].from;
}
// assert()
reverse(path+1,path+len+1);
// cout<<len<<endl;
for(int i = 1;i <= len; ++i)
id[path[i]] = i;
for(int i = 2;i <= n; ++i){
if(p[i]>=0){
int u = edges[p[i]].from;
assert(edges[p[i]].to = i);
E[u].Pb(i);
}
}
dfs(1);
// if(n == 420 )
// {
// cout<<len<<endl;
// // assert(1==0);
// }
// for(int i = 1;i <= n; ++i)
// cout<<i<<" "<<id[i]<<endl;
for(int i = 0;i < edges.size(); i ++){
if(mainpath[i>>1]) continue;
int u = edges[i].from;
int v = edges[i].to;
LL w = edges[i].w;
if(id[u] >= id[v])
continue;
// DEBUG;
// cout<<u<<" "<<v<<" "<<disf[u]+disb[v]+w<<endl;
modify(1,1,len,id[u],id[v]-1,disf[u]+disb[v]+w);
}
// cout<<"QUery"<<endl;
int e;LL noww;
for(int i = 1;i <= q; ++i){
cin>>e>>noww;e--;
LL ans = INFF;
// assert(2*e < edges.size());
int u = edges[2*e].from,v = edges[2*e].to,w = edges[2*e].w;
if(id[u] > id[v])
swap(u,v);
// cout<<w<<endl;
// if(i == 84)
// cout<<mainpath[e]<<endl;
if(mainpath[e]){
// cout<<dis[n]-w+noww<<" "<<query(1,1,len,id[u])<<endl;
ans = min(dis[n]-w+noww,query(1,1,len,id[u]));
}
else{
// cout<<u<<" "<<disf[u]<<" "<<" "<<v<<" "<<disb[v]<<endl;
ans = min(dis[n],min(disf[u]+disb[v],disf[v]+disb[u])+noww);
}
// printf("%lld\n",ans);
cout<<ans<<endl;
}
return 0;
}
