Codeforces Round #786 (Div. 3)解题报告
|
366
|
Codeforces,dp,树状数组,算法
|
starry
|
0

1163 字
|
30 分钟

读假题，写假题，人麻了

A. Number Transformation

根据题意可以很简单的发现，如果y不能被x整除就输出0 0，否则输出1 $\frac{y}{x}$即可

B. Dictionary

手推一下即有:索引为(s[0]-‘a’)*25-(s[1]>s[0])+s[1]-‘a’

C. Infinite Replacement

根据样例可以知道答案为1的情况为t串是’a’，无穷的情况是t串含’a’且长度不为1

接下来只需要考虑如何计算方案数，容易发现s串中的每个’a’仅有替换或者不被替换两种状态，所以方案数为$2^n$，其中$n$为s串长度

D. A-B-C Sort

模拟一下发现原操作仅可以交换相邻的两个，如果n为奇数，则第一个数必须为最小值

E. Breaking the Wall

写太快人麻了

容易知道得到答案的方式有相邻两个被摧毁，中间相隔一个的两个被摧毁，以及整个序列的最小两个被摧毁

对于第一种，我们需要注意是仅攻击最大值抑或是两者夹杂攻击，所以我们取max则可：ans=min(ans,max((v[i]+v[i-1]+2)/3,(max(v[i],v[i-1])+1)/2));

对于第二种，我们应该考虑到两者都为奇数时，我们只需攻击中间的即可同时使他们变为偶数，所以有：ans=min(ans,(v[i]+v[i-2]+1)/2);

对于第三种，我们仅需要维护最小与次小值即可

F. Desktop Rearrangement

读假题，人是真的麻了，还好放假人少。。。。

题意实际上是与电脑桌面图片自动编排一样，对于每次增删图标操作求最小图标移动数，我们可以每个列维护一个树状数组，也可以将坐标压成一维，维护一个树状数组即可

G. Remove Directed Edges

dp菜鸡无法可说

我们应当注意到题面(又读好久题，人麻)：

What is the maximum possible size of a cute set ? after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to 0?

所以我们可以dp，对于出度小于2的点，他的方案数为1，对于每个点，我们仅需用入度大于1的所连点去更新即可

Code:

A

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ",x)
#define pn1(x) printf("Case %d:\n",x)
#define pr2(x) printf("Case #%d: ",x)
#define pn2(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

LL tt,x,y;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
        cin>>x>>y;
        if(y%x){
            cout<<"0 0\n";
            continue;
        }
        cout<<"1 "<<y/x<<"\n";
    }
    return 0;
}

B

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;
 
const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;
 
#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ",x)
#define pn1(x) printf("Case %d:\n",x)
#define pr2(x) printf("Case #%d: ",x)
#define pn2(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
 
#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))
 
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
 
LL tt;
char x,y;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
        cin>>x>>y;
        int ans=x-'a';
        ans*=25;
        if(y>x){
            ans+=y-'a';
        }else ans+=y-'a'+1;
        cout<<ans<<"\n";
    }
    return 0;
}

C

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;
 
const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;
 
#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ",x)
#define pn1(x) printf("Case %d:\n",x)
#define pr2(x) printf("Case #%d: ",x)
#define pn2(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
 
#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))
 
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
 
LL tt;
string x,y;
 
LL quikpower(int b)
{
    LL ans = 1, base = 2;
    while (b > 0)
    {
        if (b & 1)
        {
            ans *= base;
        }
        base *= base;
        b >>= 1;
    }
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
        cin>>x>>y;
        int cnt=0;
        for(auto it:y)cnt+=(it=='a');
        if(cnt==1&&y.size()==1){
            cout<<"1\n";
            continue;
        }else if(cnt){
            cout<<"-1\n";
            continue;
        }
        cout<<quikpower(x.size())<<"\n";
    }
    return 0;
}

D

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

LL tt, n;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tt;
    f(sb, 1, tt)
    {
        cin >> n;
        vi v(n), ans;
        for (auto &it : v)
            cin >> it;
        if (n & 1)
        {
            ans.push_back(*v.begin());
            v.erase(v.begin());
        }
        int len = v.size();
        for (int i = 1; i < len; i += 2)
        {
            ans.pb(min(v[i], v[i - 1])), ans.pb(max(v[i], v[i - 1]));
        }
        int ck = is_sorted(all(ans));
        cout << (ck ? "YES\n" : "NO\n");
    }
    return 0;
}

E

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

LL tt, n;
/*
LL quikpower(int b)
{
    LL ans = 1, base = 2;
    while (b > 0)
    {
        if (b & 1)
        {
            ans *= base;
        }
        base *= base;
        b >>= 1;
    }
    return ans;
}*/

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int ans = 0x3f3f3f3f;
    vi v(n);
    for (auto &it : v)
        cin >> it;
    for(int i=1;i<n;++i){
        ans=min(ans,max((v[i]+v[i-1]+2)/3,(max(v[i],v[i-1])+1)/2));
        if(i-2>=0){
            ans=min(ans,(v[i]+v[i-2]+1)/2);
        }
    }
    sort(all(v));
    ans = min((v[0] + 1) / 2 + (v[1] + 1) / 2, ans);
    cout << ans;
    return 0;
}

F

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;


int n, m, q, a[(int)1e3 + 9][(int)1e3 + 9],x,y;

struct Bit
{
    long long a[(int)1e3+9];
    void add(int p,int k){
        while(p<=n){
            a[p]+=k;
            p+=lowbit(p);
        }
    }
    long long query(int p){
        long long res=0;
        while(p){
            res+=a[p];
            p-=lowbit(p);
        }
        return res;
    }
}b[(int)1e3+9];




int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    int sum=0;
    f(i, 1, n)
    {
        string s;
        cin >> s;
        f(j, 1, m) a[i][j] = (s[j - 1] == '*'),sum+=a[i][j];
    }
    f(i,1,n){
        f(j,1,m){
           if(a[i][j]) b[j].add(i,1);
        }
    }
    f(sb,1,q){
        cin>>x>>y;
        a[x][y]^=1;
        if(a[x][y])b[y].add(x,1),sum+=1;
        else b[y].add(x,-1),sum-=1;
        int te=sum,ans=0;
        for(int i=1;i<=m&&te;++i){
            int mi=min(te,n);
            int qu=b[i].query(mi);
            te-=mi,ans+=mi-qu;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

G

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ",x)
#define pn1(x) printf("Case %d:\n",x)
#define pr2(x) printf("Case #%d: ",x)
#define pn2(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int N=2e5+9;
int in[N],out[N],hd[N],tot,n,m,dp[N],x,y;
struct Edge
{
    int to,nxt;
}e[N];
inline void add(int u,int v){
    e[++tot]={v,hd[u]},hd[u]=tot;
}

int dfs(int u){
    if(dp[u])return dp[u];
    if(out[u]<2)return dp[u]=1;
    int ans=0;
    for(int eg=hd[u];eg;eg=e[eg].nxt){
        if(in[e[eg].to]>1)ans=max(ans,dfs(e[eg].to));
    }
    return dp[u]=ans+1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>x>>y;
        add(x,y);
        out[x]+=1,in[y]+=1;
    }
    int res=0;
    for(int i=1;i<=n;++i){
        dfs(i);
        res=max(res,dp[i]);
    }
    cout<<res;
    return 0;
}
上一篇
下一篇

推荐文章

数据结构与算法课程项目题解
求割点
Codeforces Round #851 (Div. 2)
Codeforces Round #835 (Div. 4) 解题报告
CCPC绵阳站解题报告
冬日暖心赛 题解
CCPC Final E. Elegant Tetris
多项式快速幂
NTT板子
区间最值板子