首页 > 其他分享 >ABC-278解题报告

ABC-278解题报告

时间：2023-03-01 17:34:54浏览次数：55  
标签：ABC int ll cin long ++ 解题 278 --

比赛传送门

D. All Assign Point Add

题意：给你一个数组 \(a\)，需要支持：全局赋值、单点加、单点查询。

做法一

维护最近一次全局赋值操作及每个位置在该操作后的增加量，当进行赋值操作时清空所有增加量。增加量可以用数组维护，但 STL 实现起来更简单。

By tute7627

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
	ll n;cin>>n;
	vector<ll>a(n);
	map<ll,ll>mp;
	ll last=0;
	rep(i,0,n){
		ll a;cin>>a;
		mp[i+1]+=a;
	}
	ll q;cin>>q;
	while(q--){
		ll t;cin>>t;
		if(t==1){
			ll x;cin>>x;
			last=x;
			mp.clear();
		}
		if(t==2){
			ll i,x;cin>>i>>x;
			mp[i]+=x;
		}
		if(t==3){
			ll i;cin>>i;
			cout<<mp[i]+last<<endl;
		}
	}
  return 0;
}

做法二（赛时做法）

维护最后一次赋值操作的位置（即是第几次操作），单点增加时，若之前的修改在最后一次赋值之前，则将之前的结果删掉，改为赋值的量加这次的修改。询问时比较最后一次单点加和和最后一次赋值操作哪个在后，若赋值在后，则为赋值的结果，否则为维护的结果。

By IgorI

void solve()
{
    int n;
    cin >> n;
    vll a(n);
    cin >> a;
    int q;
    cin >> q;
    ll lst_mass = -2, val = 0;
    vll lst(n, -1);
    for (int i = 0; i < q; i++)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int x;
            cin >> x;
            lst_mass = i;
            val = x;
        }
        if (t == 2)
        {
            int j, x;
            cin >> j >> x;
            j--;
            ll cur = 0;
            if (lst_mass > lst[j])
                cur = val;
            else
                cur = a[j];
            cur += x;
            lst[j] = i;
            a[j] = cur;
        }
        if (t == 3)
        {
            int j;
            cin >> j;
            j--;
            if (lst_mass > lst[j])
                cout << val << "\n";
            else
                cout << a[j] << "\n";
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    #ifdef tests
    cin >> t;
    #endif // tests
    while (t--)
    {
        solve();
    }
}

做法三

单点加、区间赋值、单点查询完全可以用线段树实现，大幅降低思维难度。

By maspy

void solve() {
  using Lazy = Lazy_CntSum_Affine<ll>;
  LL(N);
  VEC(ll, A, N);
  LazySegTree<Lazy> seg(N, [&](int i) -> pi { return {1, A[i]}; });
  LL(Q);
  FOR(Q) {
    LL(t);
    if (t == 1) {
      LL(x);
      seg.apply(0, N, {0, x});
    }
    if (t == 2) {
      LL(i, x);
      --i;
      seg.apply(i, i + 1, {1, x});
    }
    if (t == 3) {
      LL(i);
      --i;
      print(seg.get(i).se);
    }
  }
}

signed main() {
  cout << fixed << setprecision(15);

  ll T = 1;
  // LL(T);
  FOR(T) solve();

  return 0;
}

做法四（错误）

By daisybunny

#include<bits/stdc++.h>
using namespace std;
long long n,q;
long long ba;
long long m[200005],i[200005],x[200005];
long long a[200005];
vector<pair<long long,long long> > v[200005];
long long lo=-1;
int main()
{
	cin>>n;
	for(long long t=0;t<n;t++)
		cin>>a[t];
	cin>>q;
	for(long long t=0;t<q;t++)
	{
		cin>>m[t];
		if(m[t]==2)
		{
			cin>>i[t]>>x[t];
			i[t]--;
			pair<long long,long long> pr;
			pr.first=t;pr.second=x[t];
			v[i[t]].push_back(pr);
		}
		else if(m[t]==1)
		{
			cin>>x[t];
			lo=t;
		}
		else
		{
			cin>>i[t];
			i[t]--;
			long long c;
			if(lo==-1)
			{
				c=a[i[t]];
			}
			else
			{
				c=x[lo];
			}
			for(long long j=v[i[t]].size()-1;j>=0&&v[i[t]][j].first>lo;j--)
			{
				c+=v[i[t]][j].second;
			}
			cout<<c<<endl;
		}
	}
	return 0;
}

这份代码的思路为，对于单点修改，直接用每个位置一个 vector 存起来，全局赋值也存下来，询问时倒序查找 vector，只考虑在最后一次赋值操作后面的修改。

这份代码虽然 AC，但复杂度是有问题的。只要是在最后一次全局赋值之后的修改，每次询问都会扫一遍，所以复杂度可以被卡成 \(O(q^2)\)。可以这样构造数据：先在位置 \(1\) 单点修改 \(10^5\) 次，然后查询 \(10^5\) 次位置 \(1\)。每次查询都会重新处理所有的修改，故无法通过。

如果要将复杂度改正确，可以询问时将这些修改的贡献合并起来，而无需每次扫一遍。

fixed

#include<bits/stdc++.h>
using namespace std;
long long n,q;
long long ba;
long long m[200005],i[200005],x[200005];
long long a[200005];
vector<pair<long long,long long> > v[200005];
long long lo=-1;
int main()
{
	cin>>n;
	for(long long t=0;t<n;t++)
		cin>>a[t];
	cin>>q;
	for(long long t=0;t<q;t++)
	{
		cin>>m[t];
		if(m[t]==2)
		{
			cin>>i[t]>>x[t];
			i[t]--;
			pair<long long,long long> pr;
			pr.first=t;pr.second=x[t];
			v[i[t]].push_back(pr);
		}
		else if(m[t]==1)
		{
			cin>>x[t];
			lo=t;
		}
		else
		{
			cin>>i[t];
			i[t]--;
			long long c;
			if(lo==-1)
			{
				c=a[i[t]];
			}
			else
			{
				c=x[lo];
			}
			pair<long long,long long> tmp{0,0};
			while(!v[i[t]].empty()&&v[i[t]].back().first>lo)
			{
				tmp.first=v[i[t]].back().first;
				tmp.second+=v[i[t]].back().second;
				v[i[t]].pop_back();
			}
			if(tmp.second!=0)
			{
				v[i[t]].push_back(tmp);
				c+=v[i[t]].back().second;
			}
			cout<<c<<endl;
		}
	}
	return 0;
}

E. Grid Filling

题意：给你一个 \(n\times m\) 的矩阵，值域 \([1,k]\)，对于每个 \(x\times y\) 的子矩阵，求出除去该子矩阵后，剩下部分的颜色个数。

做法一

预处理出 \(sum[i][j][k]\) 表示左上角 \((1,1)-(i,j)\) 的子矩阵中有多少个 \(k\)，则对于一个子矩阵，可以对于每个 \(k\) 都 \(O(1)\) 计算出子矩阵外有多少个 \(k\)，统计一下即可。总复杂度 \(O(nmk)\)。

By Forested

int main() {
    i32 h, w, n, sh, sw;
    cin >> h >> w >> n >> sh >> sw;
    Vec<Vec<i32>> a(h, Vec<i32>(w));
    REP(i, h) REP(j, w) {
        cin >> a[i][j];
        --a[i][j];
    }

    Vec<Vec<Vec<i32>>> sum(n, Vec<Vec<i32>>(h + 1, Vec<i32>(w + 1, 0)));
    REP(i, n) {
        REP(j, h) REP(k, w) {
            sum[i][j + 1][k + 1] = sum[i][j][k + 1] + sum[i][j + 1][k] - sum[i][j][k] + (i32) (a[j][k] == i);
        }
    }

    REP(i, h - sh + 1) REP(j, w - sw + 1) {
        i32 cnt = 0;
        REP(k, n) {
            i32 cd = sum[k][i + sh][j + sw] - sum[k][i][j + sw] - sum[k][i + sh][j] + sum[k][i][j];
            if (cd < sum[k][h][w]) {
                ++cnt;
            }
        }
        cout << cnt << " \n"[j == w - sw];
    }
}

做法二

对于每个数 \(k\)，预处理出它所出现的上、下、左、右界。于是对于一个子矩阵，枚举每个 \(k\)，也可以 \(O(1)\) 判断矩阵外是否有 \(k\)：如果上下左右界全部在子矩阵内则没有，否则一定有。正确性显然。复杂度 \(O(nmk)\)。

By IgorI

void solve()
{
    int n, m, k, h, w;
    cin >> n >> m >> k >> h >> w;
    vvi a(n, vi(m));
    cin >> a;

    vi L(k, INF), R(k, -INF), U(k, INF), D(k, -INF);
    forn(i, n) forn(j, m)
    {
        a[i][j]--;
        L[a[i][j]] = min(L[a[i][j]], i);
        R[a[i][j]] = max(R[a[i][j]], i);
        U[a[i][j]] = min(U[a[i][j]], j);
        D[a[i][j]] = max(D[a[i][j]], j);
    }
    for (int i = 0; i <= n - h; i++)
    {
        for (int j = 0; j <= m - w; j++)
        {
            int x = 0;
            for (int y = 0; y < k; y++)
            {
                if (L[y] < i || R[y] >= i + h || U[y] < j || D[y] >= j + w)
                    x++;
            }
            cout << x << " ";
        }
        cout << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    #ifdef tests
    cin >> t;
    #endif // tests
    while (t--)
    {
        solve();
    }
}

做法三（赛时做法）

对于每一行，从左往右扫，动态维护矩阵外出现颜色的桶。当往右移动一格时，暴力从桶里加入一列，删掉一列即可。复杂度 \(O(n^2m)\)。

By tatyam

int main(){
    LL(H,W,N,h,w);
    VV(ll,a,H,W);
    each(v,a)each(x,v)x--;
    vec(ll,cnt,N);
    ll kinds=0;
    vv(ll,ans,H-h+1,W-w+1);
    auto add=[&](ll x,ll y){
        if(cnt[a[x][y]]++==0)kinds++;
    };
    auto remove=[&](ll x,ll y){
        if(--cnt[a[x][y]]==0)kinds--;
    };
    rep(H)rep(j,W)add(i,j);
    rep(x,h,H+1){
        rep(i,x-h,x)rep(j,w)remove(i,j);
        ans[x-h][0]=kinds;
        ll y=w;
        while(y<W){
            rep(i,x-h,x)add(i,y-w);
            rep(i,x-h,x)remove(i,y);
            y++;
            ans[x-h][y-w]=kinds;
        }
        rep(i,x-h,x)rep(j,W-w,W)add(i,j);
    }
    each(v,ans)out(v);
}

做法四

与做法三类似，每一行从左往右扫时，可以维护内部每个颜色的出现次数，判断是否等于总出现次数，如果等于则说明外部没有。复杂度 \(O(n^2m)\)。

By pengin

#include<stdio.h>
int a[302][302];
int count[302];
int cnt[302];
int main()
{
	int H, W, n, h, w;
	scanf("%d %d %d %d %d", &H, &W, &n, &h, &w);
	int i, j, k;
	for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			scanf("%d", &a[i][j]);
			a[i][j]--;
		}
	}
	for (i = 0; i < n; i++)
		count[i] = 0;
	for (i = 0; i < H; i++)
		for (j = 0; j < W; j++)
			count[a[i][j]]++;
	int res;
	for (i = 0; i <= H - h; i++)
	{
		for (k = 0; k < n; k++)
			cnt[k] = 0;
		res = 0;
		for (k = 0; k < n; k++)
			if (count[k] > 0)
				res++;
		for (k = i; k < i + h; k++)
		{
			for (j = 0; j < w; j++)
			{
				cnt[a[k][j]]++;
				if (cnt[a[k][j]] == count[a[k][j]])
					res--;
			}
		}
		printf("%d", res);
		for (j = 0; j < W - w; j++)
		{
			for (k = i; k < i + h; k++)
			{
				if (cnt[a[k][j]] == count[a[k][j]])
					res++;
				cnt[a[k][j]]--;
			}
			for (k = i; k < i + h; k++)
			{
				cnt[a[k][j + w]]++;
				if (cnt[a[k][j + w]] == count[a[k][j + w]])
					res--;
			}
			printf(" %d", res);
		}
		printf("\n");
	}
	return 0;
}

做法五

对于每个颜色，同样处理出上下左右界，考虑哪些位置的子矩阵能全部包含它们。最左上角的能包含它们的子矩阵为右下界向左上移 \((x,y)\)；最右下角的能包含它们的子矩阵自然为左上界。可以使用修改差分数组，求二维前缀和来维护。复杂度 \(O(nmk)\)。

By qwycnjwami

template<typename T>
struct Rect {
    Rect(T _t = INF, T _b = -INF, T _l = INF, T _r = -INF) : t(_t), b(_b), l(_l), r(_r) {
    }
    void add(int x, int y) {
        t = min(t, x), b = max(b, x);
        l = min(l, y), r = max(r, y);
    }

    bool empty() {
        return !(t <= b && l <= r);
    }

    T t, b, l, r;

    static const T INF = numeric_limits<T>::max();
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);


    int H, W, N, h, w;
    cin >> H >> W >> N >> h >> w;

    vector<vector<int>> A(H, vector<int>(W, 0));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
            --A[i][j];
        }
    }



    vector<Rect<int>> rects(N + 1);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            rects[A[i][j]].add(i, j);
        }
    }

    int total = 0;
    for (auto& r : rects) {
        if (!r.empty()) {
            ++total;
        }
    }
    print(total);
    vector<vector<int>> acc(H + 2, vector<int>(W + 2, 0));

    for (auto& rect : rects) {
        if (rect.empty()) {
            continue;
        }
        int t = rect.t, b = rect.b, l = rect.l, r = rect.r;
        print(t, b, l, r);
        int minX = max(0, b - (h - 1));
        int maxX = min(t, H - h);
        int minY = max(0, r - (w - 1));
        int maxY = min(l, W - w);
        print(minX, maxX, minY, maxY);
        if (minX <= maxX && minY <= maxY) {
            acc[minX + 1][minY + 1] += 1;
            acc[minX + 1][maxY + 1 + 1] -= 1;
            acc[maxX + 1 + 1][minY + 1] -= 1;
            acc[maxX + 1 + 1][maxY + 1  + 1] += 1;
        }
    }

    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            acc[i][j] += acc[i][j - 1] + acc[i - 1][j] - acc[i - 1][j - 1];
        }
    }
    // for (auto& V : acc) {
    //     print(V);
    // }


    for (int i = 0; i + h <= H; ++i) {
        for (int j = 0; j + w <= W; ++j) {
            auto ans = total - acc[i + 1][j + 1];
            write << ans << (j + w == W ? '\n' : ' ');
        }
    }

    return 0;
}

F. Shiritori

题意：给你 \(n\) 个字符串，两个人轮流拿走字符串，要求拿走的字符串的首必须等于上一次拿走的字符串的尾。第一次可以拿任意字符串。问先手必胜还是后手必胜。

一个显然的状压 DP。定义 \(f[mask][i]\) 表示当前集合为 \(mask\)，上一次选了字符串 \(i\)；或者 \(f[mask][c]\) 表示当前集合为 \(mask\)，上一次的末尾字符为 \(c\)，接下来先手必胜还是后手必胜。转移时只能选择剩余的，能匹配的字符串转移。对于第一次操作任意选特殊处理一下即可。可以用循环也可以用记忆化搜索。

循环写法

By maspy

void solve() {
  LL(N);
  VEC(string, S, N);
  // 残り文字列、直前 -> 先手はかつか？
  vv(bool, DP, 1 << N, N);
  FOR(s, 1 << N) {
    FOR(i, N) {
      vi cand;
      FOR(j, N) {
        if (!(s & 1 << j)) continue;
        if (S[i].back() != S[j][0]) continue;
        cand.eb(j);
      }
      for (auto&& j: cand) {
        int t = s - (1 << j);
        assert(s > t);
        if (DP[t][j] == 0) DP[s][i] = 1;
      }
    }
  }

  FOR(i, N) {
    ll full = (1 << N) - 1;
    ll s = full - (1 << i);
    if (DP[s][i] == 0) return print("First");
  }
  print("Second");
}

signed main() {
  cout << fixed << setprecision(15);

  ll T = 1;
  // LL(T);
  FOR(T) solve();

  return 0;
}

记搜写法

By Forested

int main() {
    constexpr i32 S = 26;
    i32 n;
    cin >> n;
    Vec<i32> a(n), b(n);
    REP(i, n) {
        string s;
        cin >> s;
        a[i] = s[0] - 'a';
        b[i] = s.back() - 'a';
    }

    Vec<Vec<i32>> memo(n, Vec<i32>(1 << n, -1));
    const auto dp = [&](const auto &dp, i32 lst, i32 used) -> i32 {
        if (used == (1 << n) - 1) {
            return 1;
        }
        if (memo[lst][used] != -1) {
            return memo[lst][used];
        }
        REP(i, n) {
            if (used & (1 << i)) {
                continue;
            }
            if (used != 0 && b[lst] != a[i]) {
                continue;
            }
            if (dp(dp, i, used ^ (1 << i)) == 1) {
                return memo[lst][used] = 0;
            }
        }
        return memo[lst][used] = 1;
    };
    i32 winner = dp(dp, 0, 0);
    cout << (winner == 0 ? "First\n" : "Second\n");
}

标签：ABC,int,ll,cin,long,++,解题,278,--
From： https://www.cnblogs.com/cxm1024/p/17168382.html

相关文章

  • ABC-277解题报告
    比赛传送门B.PlayingCardsValidation题意：有\(n\)个长度为\(2\)的字符串，判断是否满足以下条件：第一个字符为HDCS之一。第二个字符为A23456789TJQK之一。字......
  • ABC-282解题报告
    比赛传送门C.StringDelimiter题意：有一个包含字母、双引号（保证有偶数个，相邻两个匹配）和逗号的字符串，将在双引号外的逗号改为句号。维护当前在双引号里还是外，遇到双引......
  • ABC-280解题报告
    D.FactorialandMultiple题意：给你一个\(k\)，求最小的\(n\)使得\(k|n!\)。\(k\le10^{12}\)。做法一考虑将\(k\)分解质因数，对于每项\(p^r\)，都要求\(n!\)中含......
  • ABC-279解题报告
    比赛传送门C.RANDOM题意：给你两个01矩阵\(S,T\)，问是否可以将\(S\)以列为单位重新排列得到\(T\)。判断\(S,T\)的每列是否可以一一对应即可做法一以列为单位......
  • ABC-288解题报告
    比赛传送门D.RangeAddQuery题意：有一个序列\(A\)和正整数\(k\)，每次询问给定\(l,r\)，你可以在\([l,r]\)内选择一段长度为\(k\)的子段，统一加减，问是否能将\([l,r......
  • ABC-271解题报告
    C.Manga题意：有一本书有\(n\)卷，你需要从第一卷开始依次看，一旦没有某一卷就停止。在看之前你可以进行若干次操作，每次卖掉任意两卷并买新的任意一卷。问操作结束后最多能......
  • AGC-059解题报告
    比赛传送门A.MyLastABCProblem题意：有一个只含ABC字符串\(s\)，每次询问一段区间\([l,r]\)，问至少需要多少次操作能将这段区间变得完全相同。每次操作可以选一段区......
  • ABC275D-Yet-Another-Recursive-Function题解
    题目传送门题意：定义一个\(\mathbb{N}\to\mathbb{N}\)的函数\(f(x)=\begin{cases}1&x=0\\f(\lfloor\frac{x}{2}\rfloor)+f(\lfloor\frac{x}{3}\rfloor)&\text{otherwis......
  • CFR-826-Div-3解题报告
    F.Multi-ColoredSegments题意：数轴上有\(n\)个线段，每个区间有一个颜色\(c\)，对于每个线段，求与它颜色不同的线段中与它的最短距离。距离定义为两个线段中的点集最近的......
  • CFR-832-Div-2解题报告
    B.BANBAN题意：给你一个\(n\)，生成一个字符串为BAN重复\(n\)遍。每次操作可以选择两个位置进行交换，问至少多少次交换后可以使该串不存在BAN的子序列。输出方案。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99