练习3

practise

A hesorchen

//https://blog.csdn.net/hesorchen
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define lowbit(a) (a & (-a))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define endl "\n"
#define MAX 100010
int p[5];
int main()
{
    cin >> p[0] >> p[1] >> p[2];
    sort(p, p + 3);
    int ans = 0;
    ans += (p[2] - p[0]) / 2;
    p[0] += ((p[2] - p[0]) / 2) * 2;
    ans += (p[2] - p[1]) / 2;
    p[1] += ((p[2] - p[1]) / 2) * 2;
    // cout << ans << endl;
    sort(p, p + 3);
    if (p[0] == p[2])
        ans += 0;
    else if (p[1] == p[2])
        ans += 2;
    else if (p[1] == p[0])
        ans += 1;
    cout << ans << endl;
    return 0;
}

B hesorchen

//https://blog.csdn.net/hesorchen
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define lowbit(a) (a & (-a))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define endl "\n"
#define MAX 100010
struct node
{
    int s, e;
} p[100005];
bool cmp(node a, node b)
{
    if (a.s = b.s)
        return a.e < b.e;
    return a.s < b.s;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i].s >> p[i].e;
    sort(p, p + n, cmp);
    int ans = 0;
    int t1, t2;
    t1 = -2;
    t2 = -2;
    for (int i = 0; i < n; i++)
    {
        if (p[i].s <= t1)
        {
            continue;
        }
        else if (p[i].s <= t2)
        {
            t1 = t2;
            t2 = p[i].e;
            ans++;
        }
        else
        {
            ans += 2;
            t1 = p[i].e - 1;
            t2 = p[i].e;
        }
    }
    cout << ans << endl;
    return 0;
}

C 194215091012

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
void convert1(int n,char str[]);
void convert2(int n,char str[]);
int i,j;
int main()
{
    int n,m;
    int ans=0;
    char a[10000];
    char b[10000];
    scanf("%d",&n);
    m=n-1;
    convert1(n,a);
    convert2(m,b);
    for(int c=0;c<i;c++)
    {
        if(a[c]!=b[c])
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}
void convert1 (int n,char str[])
{
          i=0;
    if(n==0)
        printf("0\n");
    while(n>0)
    {
        str[i++]=n%2+'0';
        n=n/2;
    }
}
void convert2 (int n,char str[])
{
       j=0;
    if(n==0)
        printf("0\n");
    while(n>0)
    {
        str[j++]=n%2+'0';
        n=n/2;
    }
}

D 184215092008

python

a = int(input(""))
list = []
if(a == 0):
    list.append(0)
while(a):
    if(a%(-2)==0):
        list.append(0)
        a//=-2
    elif(a%(-2)==-1):
        list.append(1)
        a -= 1
        a//=-2
list.reverse()
for i in list:print(i,end='')
print()

E _Wallace_

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef unsigned long long LL;
const int N=260+5;
const LL base=2333333;
char A[N],B[N];
LL pw[N],x[N],y[N];
int la,lb;
vector<LL> h;
bool judge(int len)
{
    h.clear();
    for(register int i=len;i<=la;i++)
    {
        LL tmp=x[i]-x[i-len]*pw[len];
        h.push_back(tmp);
    }
    sort(h.begin(),h.end());
    for(register int i=len;i<=lb;i++)
    {
        LL tmp=y[i]-y[i-len]*pw[len];
        if(binary_search(h.begin(),h.end(),tmp))
            return true;
    }
    return false;
}
void solve()
{
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    la=strlen(A+1);
    lb=strlen(B+1);
    for(register int i=la+1;i<=la*2;i++)
        A[i]=A[i-la];
    for(register int i=lb+1;i<=lb*2;i++)
        B[i]=B[i-lb];
    la*=2,lb*=2;
    for(register int i=1;i<=la;i++)
        x[i]=x[i-1]*base+A[i];
    for(register int i=1;i<=lb;i++)
        y[i]=y[i-1]*base+B[i];
    int L=0,R=min(la,lb)/2,ret=0;
    while(L<=R)
    {
        int mid=(L+R)>>1;
        if(judge(mid)) L=mid+1,ret=mid;
        else R=mid-1;
    }
    printf("%d\n",ret);
}
signed main()
{
    pw[0]=1llu;
    for(register int i=1;i<=260;i++)
        pw[i]=pw[i-1]*base;
    while(scanf("%s%s",A+1,B+1)!=EOF) solve();
    return 0;
}

F _Wallace_

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int N=2e3+5;
bool f[N][N];
string a,b,c;
bool solve()
{
    if(a.size()+b.size()!=c.size()) return false;
    memset(f,0,sizeof(f)),f[0][0]=1;
    for(register int i=0;i<=a.size();i++)
        for(register int j=0;j<=b.size();j++)
        {
            if(c[i+j]==a[i])
                f[i+1][j]|=f[i][j];
            if(c[i+j]==b[j])
                f[i][j+1]|=f[i][j];
        }
    return f[a.size()][b.size()];
}
signed main()
{
    while(cin>>a>>b>>c)
        if(solve()) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    return 0;
}

G lnkkerst

#include <cstdio>
#include <cctype>
#include <cmath>
#define int long long
int read() {
    int ret, fl = 1;
    char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (fl = -1);
    for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
    return ret * fl;
}
void print(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
signed main() {
    int t = read();
    while(t--) {
        int a = read(), b = read(), mul = a * b;
        int base = (int)sqrt(mul), ans = (base << 1);
        // if(base == a && base == b) --ans;
        // // if(abs(a - b) == 1 && (base == a || base == b)) --ans;
        // if(base * base == mul - 1) --ans;
        // if(base * base == mul) ans -= 2;
        if(base * base == mul) {
            if(a == b) ans -= 2;
            else ans -= 3;
        }
        else if(base * (base + 1) < mul) ans -= 1;
        else ans -= 2;
        print(ans), putchar('\n');
    }
    return 0;
}

H hesorchen

//https://blog.csdn.net/hesorchen
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define lowbit(a) (a & (-a))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define endl "\n"
#define MAX 100010
string a;
stack<char> st;
string ans;
int main()
{
    int n;
    cin >> n >> a;
    int c = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] == '(')
        {
            c++;
            ans = ans + '(';
        }
        else
        {
            c--;
            if (c>=0)
                ans = ans + ')';
            else
            {
                c++;
                ans = '(' + ans + ")";
            }
        }
    }
    while (c--)
    {
        ans = ans + ')';
    }
    cout << ans << endl;
    return 0;
}

I 6109118071

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cmath>
#include<map>
#include<bitset>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define M 112300
int n, f[25] = {0, 0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};
int main(){
    while (~scanf("%d", &n) && n)
        printf("%d %d\n", n, f[n]);
}

J Kevin7Zz

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue> //priority_queue 优先队列
#include <map>
#include <set> //multiset  
#include <vector>
#include <stack>
#include <cmath>
#include <sstream>
#include <string>
#define mod 1000000007
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
const db eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
using namespace std;
int q,n,k;
string s,t="RGB";
int main(){
    cin>>q;
    while(q--){
        cin>>n>>k;
        cin>>s;
        int ans=INF;
        for(int i=0;i<3;i++){
            int cur=0;
            vector<int> res(n);
            for(int j=0;j<n;j++){
                res[j]=(s[j]!=t[(i+j)%3]);
                cur+=res[j];
                if(j>=k) cur-=res[j-k];
                if(j>=k-1) ans=min(ans,cur);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}