T1 机器人
题解
傻逼题，但是有人 \(90\) 分
一开始十分想直接暴力 \(2^n\) 判断每一步选不选求出所有可能性
但是会发现它有制约关系有些步走了之后，有些就必须走了
所以需要用一个数组记录当前位置走没走过，或者是不是障碍
注意走没走过不能直接赋值 \(1,0\) 因为回溯时会直接将前面的标记也改没了
还要注意的一点是对于部分实现来说遍历顺序很重要，可能会卡住几个点
也是因为标记顺序导致的，容易破坏之前的标记导致状态错误
#include<bits/stdc++.h>
#define N 40
using namespace std;
int n,ans,g[N<<1][N<<1],vis[N<<1][N<<1];
char s[N];
void dfs(int p,int x,int y){
if(p==n+1){
if(!g[x][y])ans++;
g[x][y] = 1;
return ;
}
int fx = x,fy = y;
switch(s[p]){
case'L':x--;break;
case'R':x++;break;
case'U':y++;break;
case'D':y--;break;
}
if(vis[x][y]==0){
vis[x][y] = -1;
dfs(p+1,fx,fy);
vis[x][y] = 1;
dfs(p+1,x,y);
vis[x][y]=0;
}
else if(vis[x][y]==-1)dfs(p+1,fx,fy);
else if(vis[x][y]==1)dfs(p+1,x,y);
}
int main(){
freopen("robot.in","r",stdin);
freopen("robot.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>s+1;vis[n][n]=1;
dfs(1,n,n);
cout<<ans<<"\n";
for(int i = 0;i<=n*2;i++)
for(int j = 0;j<=n*2;j++)
if(g[i][j]) cout<<i-n<<" "<<j-n<<"\n";
return 0;
}
T2 旅行
题解
先考虑是一棵树的情况时色块数的贡献，我们以每个节点为分界点计算答案
该节点对答案的贡献即为不同颜色的数目减一，对于每次修改操作，统计节点的增量即可
基环树是一个环上每一个节点连接了一棵树，和树的情况类似
节点的贡献是相同计算的，同时要考虑环多出的那一条边对答案的贡献，如果整个环上只有一种颜色, 答案还要加一
只需使用 \(map\) 代替二维数组记录每个点内不同颜色的数量，再 \(dfs\) 找出所有环上的边，判断这些边的颜色是否相同即可统计单次答案
一次修改最多改一条边上的值，所以可以方便的进行单点修改同时维护答案
#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n,q,rt,col[N],hcol[N],h[N];
bool vis[N];
vector<int>g[N];
map<pair<int,int>,int>id;
map<int,int>mp[N];
int dfs(int u,int fa){
vis[u] = 1;
int x = 0;
for(int v : g[u]){
if(v==fa) continue;
if(!vis[v]){
int tmp = dfs(v,u);
if(tmp){
int fu = u,fv = v;
if(fu>fv) swap(fu,fv);
h[id[{fu,fv}]] = 1;
x = tmp;
}
if(tmp==u) x = 0;
}else if(v!=rt){
int fu = u,fv = v;
if(fu>fv) swap(fu,fv);
h[id[{fu,fv}]] = 1;
rt = u;x = v;
}
}
return x;
}
int main(){
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--){
cin>>n>>q;rt = 0;
id.clear();
for(int i = 1;i<=n;i++){
g[i].clear();mp[i].clear();
h[i] = vis[i] = hcol[i] = 0;
}
for(int i = 1;i<=n;i++){
int u,v,w;
cin>>u>>v>>w;
if(u>v) swap(u,v);
id[{u,v}] = i;
col[i] = w;
mp[u][w]++;mp[v][w]++;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
int ans = 0;
for(int i = 1;i<=n;i++)
ans+=mp[i].size()-1;
int hsize = 0;
for(int i = 1;i<=n;i++)
if(h[i]) hsize++;
for(int i = 1;i<=n;i++){
if(h[i]){
hcol[col[i]]++;
if(hcol[col[i]]==hsize) ans++;
}
}
for(int i = 1;i<=q;i++){
int u,v,w;
cin>>u>>v>>w;
if(u>v) swap(u,v);
int p = id[{u,v}];
if(h[p]){
if(hcol[col[p]]==hsize) ans--;
hcol[col[p]]--;
hcol[w]++;
if(hcol[w]==hsize) ans++;
}
mp[u][col[p]]--;
if(!mp[u][col[p]]) ans--;
if(!mp[u][w]) ans++;
mp[u][w]++;
mp[v][col[p]]--;
if(!mp[v][col[p]]) ans--;
if(!mp[v][w]) ans++;
mp[v][w]++;
col[p] = w;
cout<<ans<<"\n";
}
}
return 0;
}
T3 点餐
题解
将所有输入先按照 \(b\) 排序，枚举第 \(x\) 道菜作为最大的 \(b\) 值的答案，贪心选择前面 \(k-1\) 个 \(a\) 更小的即可
可以通过可持久化线段树 \(\mathcal O(\log n)\) 求出答案 \(f_{k,x}\)
设 \(g_k\) 表示选择 \(k\) 个时最优解是选择 \(x\) 作为 \(b\) 最大
对于两个决策 \(x,y(x<y)\) 如果 \(f_{x,k} \ge f_{y,k}\) 那么对于 \(k(k\le x)\) ，\(y\) 的选择范围一定包含 \(x\) 的选择范围，因此 \(y\) 选的 \(a\) 值一定不大于 \(x\) 选的
所以有 \(g_1 \le g_2 \le g_3 \ldots \le g_n\) ，也就是具有决策单调性，可以分治求解
时间复杂度为 \(\mathcal O(n \log ^2 n)\)
#include<bits/stdc++.h>
#define int long long
#define N 200010
#define M ((60*N)+5)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
struct node{
int l,r,dat,sum;
}t[M];
int n,m,cnt,tot,hs[N],rt[N],ans[N];
pii a[N];
bool cmp(pii x,pii y){
return x.se<y.se;
}
void newnode(int &v){
t[++cnt].dat = t[v].dat;
t[cnt].sum = t[v].sum;
t[cnt].l = t[v].l;
t[cnt].r = t[v].r;
v = cnt;
}
void insert(int x,int &v,int l,int r){
newnode(v);
t[v].dat++;
t[v].sum+=hs[x];
if(l==r) return ;
int mid = (l+r)>>1;
if(x<=mid) insert(x,t[v].l,l,mid);
else insert(x,t[v].r,mid+1,r);
}
int query(int p,int v,int l,int r){
if(l==r) return p*hs[l];
int mid = (l+r)>>1;
if(t[t[v].l].dat>=p) return query(p,t[v].l,l,mid);
else return t[t[v].l].sum+query(p-t[t[v].l].dat,t[v].r,mid+1,r);
}
void calc(int x,int y,int l,int r){
if(l>r||x>y) return ;
int mid = (l+r)>>1,p = 0;
ans[mid] = 1e18;
for(int i = max(x,mid);i<=y;i++){
int w = a[i].se+query(mid,rt[i],1,tot);
if(w<ans[mid]) ans[mid] = w,p = i;
}
calc(x,p,l,mid-1);
calc(p,y,mid+1,r);
}
signed main(){
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i<=n;i++){
cin>>a[i].fi>>a[i].se;
hs[i] = a[i].fi;
}
sort(hs+1,hs+n+1);
tot = unique(hs+1,hs+n+1)-hs-1;
for(int i = 1;i<=n;i++)
a[i].fi = lower_bound(hs+1,hs+tot+1,a[i].fi)-hs;
sort(a+1,a+n+1,cmp);
for(int i = 1;i<=n;i++){
rt[i] = rt[i-1];
insert(a[i].fi,rt[i],1,tot);
}
calc(1,n,1,n);
for(int i = 1;i<=n;i++)
cout<<ans[i]<<"\n";
return 0;
}
又是不会T4的一天
标签：校内,int,++,231019,mp,ans,col,define From： https://www.cnblogs.com/cztq/p/17775642.html