练习10

practise

A Carered

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
const int inf=0x3f3f3f3f;
ll n,k;
int main(){
    cin >> n >> k;
    if(2LL * k >= n){
        cout << 10 << endl;
    }
    else{
            if(n % k != 0)
                cout << (n/k+1) *5LL <<endl;
            else cout << n/k *5LL << endl;
    }
    return 0;
}

B 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int prime[50010],p;
int main(){
    rep(i,3,50005){
        int flag=1;
        for(int j=2;j*j<=i;j++){
            if(i%j==0){
                flag=0;break;
            }
        }
        if(flag&&i%5==1){
            prime[++p]=i;
        }
    }
    int n;cin>>n;
    rep(i,1,n){
        printf("%d%c",prime[i],(i==n)?'\n':' ');
    }
    return 0;
}

C 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int n,k,s,t,big=1e9;
int main(){
    cin>>n>>k>>s;
    if(s==big){
        t=s-1;
    }
    else{
        t=big;
    }
    rep(i,1,n){
        if(i<=k){
            printf("%d ",s);
        }
        else{
            printf("%d ",t);
        }
    }puts("");
    return 0;
}

D 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int n,ans=1e9;
char s[100010];
int main(){
    cin>>n;
    scanf("%s",s+1);
    int r=0,b=0;
    rep(i,1,n){
        if(i%2==1&&s[i]=='r'){
            r++;
        }
        else if(i%2==0&&s[i]=='b'){
            b++;
        }
    }
    ans=min(ans,min(r,b)+abs(r-b));
    r=0,b=0;
    rep(i,1,n){
        if(i%2==1&&s[i]=='b'){
            r++;
        }
        else if(i%2==0&&s[i]=='r'){
            b++;
        }
    }
    ans=min(ans,min(r,b)+abs(r-b));
    cout<<ans<<endl;
    return 0;
}

E Carered

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2000 + 50;
typedef pair<int, int> pii;
pii p[maxn], q[maxn];
int n, Q;
int ans[maxn];
pii get_v(int x1, int y1, int x2, int y2){
    int x = x1 - x2, y = y1 - y2;
    int d = __gcd(x, y);
    x /= d, y /= d;
    if(x < 0) return make_pair(-x, -y);
    else{
        if(x == 0 && y < 0) return make_pair(x, -y);
    }
    return make_pair(x, y);
}
int main()
{
    std::ios::sync_with_stdio(false);
    while(cin >> n >> Q){
        for(int i = 0;i < n;i++){
            cin >> p[i].first >> p[i].second;
        }
        for(int i = 0;i < Q;i++){
            cin >> q[i].first >> q[i].second;
            ans[i] = 0;
        }
        map<pii, int> mp;
        for(int i = 0;i < Q;i++){
            mp.clear();
            for(int j = 0;j < n;j++){
                pii v = get_v(p[j].first, p[j].second, q[i].first, q[i].second);
                mp[v]++;
                v = get_v(p[j].second, q[i].first, q[i].second, p[j].first);
                if(mp.count(v)) ans[i] += mp[v];
            }
        }
        for(int i = 0;i < n;i++){
            mp.clear();
            for(int j = 0;j < n;j++){
                if(i == j) continue;
                pii v = get_v(p[j].first, p[j].second, p[i].first, p[i].second);
                mp[v]++;
            }
            for(int j = 0;j < Q;j++){
                pii v = get_v(p[i].second, q[j].first, q[j].second, p[i].first);
                if(mp.count(v)) ans[j] += mp[v];
            }
        }
        for(int i = 0;i < Q;i++) cout << ans[i] << endl;
    }
    return 0;
}

F 1292224662

#include<bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
typedef pair<int,int> pii;
int n,f,t;
vector<int> g[200010];
int fa[200010];
pii dfs(int now,int f,int len=0){
    fa[now]=f;
    pii res={now,len};
    for(auto t:g[now]){
        if(t==f)    continue;
        pii tmp=dfs(t,now,len+1);
        if(tmp.yy>res.yy){
            res=tmp;
        }
    }
    return res;
}
bool vis[200010];
int dis[200010];
queue<int> q;
pii bfs(){
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(auto t:g[now]){
            if(!vis[t]){
                dis[t]=min(dis[t],dis[now]+1);
                q.push(t);
                vis[t]=1;
            }
        }
    }
    pii res={-1,-1};
    for(int i=1;i<=n;i++){
        if(dis[i]>res.yy){
            res.xx=i;
            res.yy=dis[i];
        }
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&f,&t);
        g[f].push_back(t);
        g[t].push_back(f);
    }
    pii p1=dfs(1,-1);
    pii p2=dfs(p1.xx,-1);
    printf("%d\n",p2.second);
    return 0;
}

G 2018031701054

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 7 + 1e5;
const int mod = 3 + 1e5;
struct {
    int next;
    int a[6];
} E[N];
int head[N], tot;
int a[6];
int n;
int get(int* a) {
    int sum = 0, mul = 1;
    for (int i = 0; i < 6; ++i) {
        sum += a[i];
        mul = 1LL * mul * a[i] % mod;
    }
    return (sum + mul) % mod;
}
int equal(int* a, int* b) {
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            int ok = 1;
            for (int k = 0; k < 6 && ok; ++k) {
                if (a[(i + k) % 6] != b[(j + k) % 6]) ok = 0;
            }
            if (ok) return 1;
            ok = 1;
            for (int k = 0; k < 6 && ok; ++k) {
                if (a[(i + k) % 6] != b[(j - k + 6) % 6]) ok = 0;
            }
            if (ok) return 1;
        }
    }
    return 0;
}
int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        for (int i = 0; i < 6; ++i)
            scanf("%d", a + i);
        int x = get(a);
        for (int i = head[x]; i; i = E[i].next) {
            if (equal(a, E[i].a)) {
                printf("Twin snowflakes found.\n");
                return 0;
            }
        }
        memcpy(E[++tot].a, a, sizeof a);
        E[tot].next = head[x];
        head[x] = tot;
    }
    printf("No two snowflakes are alike.\n");
    return 0;
}

H likailin

#include<iostream>
#include<cstring>
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define VI vector<int>
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define il inline
#define int long long
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define pi 3.14159265358979323
#define debug(x)              cout <<#x<<": "<<x<<endl;
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
/*
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int inf (0x3f3f3f3f);
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}
ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=0,v=a;while(b){if(b&1){r+=v;if(r>p)r-=p;}v<<=1;if(v>p)v-=p;b>>=1;}return r;}
ll quick_pow(ll a,ll b,ll p){ll r=1,v=a%p;while(b){if(b&1)r=mult(r,v,p);v=mult(v,v,p);b>>=1;}return r;}
bool CH(ll a,ll n,ll x,ll t)
{ll r=quick_pow(a,x,n);ll z=r;for(ll i=1;i<=t;i++){r=mult(r,r,n);if(r==1&&z!=1&&z!=n-1)return true;z=r;}return r!=1;}
bool Miller_Rabin(ll n)
{if(n<2)return false;if(n==2)return true;if(!(n&1))return false;ll x=n-1,t=0;while(!(x&1)){x>>=1;t++;}srand(time(NULL));
ll o=8;for(ll i=0;i<o;i++){ll a=rand()%(n-1)+1;if(CH(a,n,x,t))return false;}return true;}
void exgcd(ll a,ll b ,ll &x,ll &y){if(!b){x=1,y=0;return;}exgcd(b,a%b,x,y);ll t=x;x=y,y=t-(a/b)*y;}
ll inv(ll a,ll b){ll x,y;return exgcd(a,b,x,y),(x%b+b)%b;}
ll crt(ll x,ll p,ll mod){return inv(p/mod,mod)*(p/mod)*x;}
ll fac(ll x,ll a,ll b)
{if(!x)return 1;ll ans=1;for(ll i=1;i<=b;i++)if(i%a)ans*=i,ans%=b;
ans=pow_mod(ans,x/b,b);for(ll i=1;i<=x%b;i++)if(i%a)ans*=i,ans%=b;return ans*fac(x/a,a,b)%b;}
ll C(ll n,ll m,ll a,ll b)
{ll N=fac(n,a,b),M=fac(m,a,b),Z=fac(n-m,a,b),sum=0,i;for(i=n;i;i=i/a)sum+=i/a;
for(i=m;i;i=i/a)sum-=i/a;for(i=n-m;i;i=i/a)sum-=i/a;return N*pow_mod(a,sum,b)%b*inv(M,b)%b*inv(Z,b)%b;}
ll exlucas(ll n,ll m,ll p)
{ll t=p,ans=0,i;for(i=2;i*i<=p;i++){ll k=1;while(t%i==0){k*=i,t/=i;}
ans+=crt(C(n,m,i,k),p,k),ans%=p;}if(t>1)ans+=crt(C(n,m,t,t),p,t),ans%=p;return ans % p;}
int prime[100000],minprime[100000];
void euler(int n)
{int c=0,i,j;for(i=2;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=1;j<=c&&i*prime[j]<=n;j++)
{minprime[i*prime[j]]=prime[j];if(i%prime[j]==0)break;}}}
struct Tree{ll l,r,sum,lazy,maxn,minn;}tree[100000];
il void push_up(ll rt)
{tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
tree[rt].maxn=max(tree[rt<<1].maxn,tree[rt<<1|1].maxn);
tree[rt].minn=min(tree[rt<<1].minn,tree[rt<<1|1].minn);}
il void push_down(ll rt , ll length)
{if(tree[rt].lazy){tree[rt<<1].lazy+=tree[rt].lazy;tree[rt<<1|1].lazy+=tree[rt].lazy;
tree[rt<<1].sum+=(length-(length>>1))*tree[rt].lazy;tree[rt<<1|1].sum+=(length>>1)*tree[rt].lazy;
tree[rt<<1].minn+=tree[rt].lazy;tree[rt<<1|1].minn+=tree[rt].lazy;
tree[rt<<1].maxn+=tree[rt].lazy;tree[rt<<1|1].maxn+=tree[rt].lazy;tree[rt].lazy=0;}}
il void build(ll l , ll r , ll rt , ll *aa)
{tree[rt].lazy=0;tree[rt].l=l;tree[rt].r=r;if(l==r)
{tree[rt].sum=aa[l];tree[rt].minn=tree[rt].sum;tree[rt].maxn=tree[rt].sum;return;}
ll mid=(l+r)>>1;build(l,mid,rt<<1,aa);build(mid+1,r,rt<<1|1,aa);push_up(rt);}
il void update_range(ll L , ll R , ll key , ll rt)
{if(tree[rt].r<L||tree[rt].l>R)return;if(L<=tree[rt].l&&R>=tree[rt].r){tree[rt].sum+=(tree[rt].r-tree[rt].l+1)*key;
tree[rt].minn+=key;tree[rt].maxn+=key;tree[rt].lazy+=key;return;}push_down(rt,tree[rt].r-tree[rt].l+1);
ll mid=(tree[rt].r+tree[rt].l)>>1;if(L<=mid)update_range(L,R,key,rt << 1);
if(R>mid)update_range(L,R,key,rt << 1 | 1);push_up(rt);}
il ll query_range(ll L, ll R, ll rt)
{if(L<=tree[rt].l&&R>=tree[rt].r){return tree[rt].sum;}push_down(rt,tree[rt].r-tree[rt].l+1);
ll mid=(tree[rt].r+tree[rt].l)>>1;ll ans=0;if(L<=mid)ans+=query_range(L,R,rt << 1);
if(R>mid)ans+=query_range(L,R,rt << 1 | 1);return ans;}
il ll query_min(ll L,ll R,ll rt)
{if(L<=tree[rt].l&&R>=tree[rt].r){return tree[rt].minn;}push_down(rt,tree[rt].r-tree[rt].l+1);
ll mid=(tree[rt].r+tree[rt].l)>>1;ll ans=(0x3f3f3f3f3f3f3f3fll);if(L<=mid)ans=min(ans,query_min(L,R,rt << 1));
if(R>mid)ans=min(ans,query_min(L,R,rt << 1 | 1));return ans;}
il ll query_max(ll L, ll R, ll rt)
{if(L<=tree[rt].l&&R>=tree[rt].r){return tree[rt].maxn;}push_down(rt,tree[rt].r-tree[rt].l+1);
ll mid=(tree[rt].r+tree[rt].l)>>1;ll ans=-(0x3f3f3f3f3f3f3f3fll);if(L<=mid)ans=max(ans,query_max(L,R,rt << 1));
if(R>mid)ans=max(ans,query_max(L,R,rt << 1 | 1));return ans;}
*/
const int N=50050,P=1e9+7;
int n,a[N],b[N];
struct Node{
    int len; ll cnt;
    void operator += (const Node &b){
        if(b.len < len) return;
        else if(b.len > len) cnt = b.cnt, len = b.len;
        else cnt = (cnt + b.cnt) % P;
    }
}f[N],c[N],ans;
Node Quary(int x){
    Node tmp = {0,1};
    for(;x;x-=x&-x) tmp += c[x];
    return tmp;
}
void Update(int x,Node val){
    for(;x<=n;x+=x&-x) c[x] += val;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]); b[i] = a[i];
    } sort(b+1,b+n+1);
    int siz = unique(b+1,b+n+1) - (b+1);
    for(int i=1;i<=n;i++) a[i] = lower_bound(b+1,b+siz+1,a[i]) - b;
    for(int i=1;i<=n;i++){
        f[i] = Quary(a[i]-1);
        f[i].len ++;
        ans += f[i];
        Update(a[i],f[i]);
    } printf("%lld",ans.cnt); return 0;
}

I Slove_code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <queue>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
using namespace std;
#define inf 1 << 28
typedef long long ll;
const ll maxn = 5e3 + 5;
ll tr[maxn][maxn], n, m;
ll lowbit(ll x)
{
    return (x) & (-x);
}
void add(ll x, ll y, ll v)
{
    while (x <= n)
    {
        ll ty = y;
        while (ty <= m)
        {
            tr[x][ty] += v;
            ty += lowbit(ty);
        }
        x += lowbit(x);
    }
}
void real_add(ll x1, ll y1, ll x2, ll y2, ll v)
{
    add(x1, y1, v);
    add(x1, y2 + 1, -v);
    add(x2 + 1, y1, -v);
    add(x2 + 1, y2 + 1, v);
}
ll ask(ll x, ll y)
{
    ll res = 0;
    while (x)
    {
        ll ty = y;
        while (ty)
            res += tr[x][ty], ty -= lowbit(ty);
        x -= lowbit(x);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n >> m)
    {
        memset(tr, 0, sizeof tr);
        ll a, b, c, d, e, k;
        while (cin >> a)
        {
            if (a & 1)
            {
                cin >> b >> c >> d >> e >> k;
                real_add(b, c, d, e, k);
            }
            else
            {
                cin >> b >> c;
                if (b > n || c > m)
                    cout << 0 << endl;
                else
                    cout << ask(b, c) << endl;
            }
        }
    }
}

J puluo

#include<stdio.h>
bool used[1005];
int heng[105],zong[105],he[105][105],cnt=0;
long long sum;
/*二分图*/
int num,to[70005],next[70005],head[1005],match[1005];
void makeline(int u,int v)
{
    to[++cnt]=v;
    next[cnt]=head[u];
    head[u]=cnt;
}
bool mat(int u)
{
    for(int edge=head[u];edge;edge=next[edge])
    if(used[to[edge]]==false)
    {
        int k,v=to[edge];
        k=match[v];used[v]=1;match[v]=u;
        if(!k||mat(k))return true;
        match[v]=k;
    }
    return false;
}
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)scanf("%d",&he[i][j]);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(heng[i]<he[i][j])heng[i]=he[i][j];
            if(zong[j]<he[i][j])zong[j]=he[i][j];
            /*贪心*/
            if(he[i][j]>0)sum+=he[i][j]-1;
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        if(heng[i]==zong[j]&&he[i][j]!=0)makeline(i,m+j);
    }
    /*返还投影*/
    for(int i=1;i<=m;i++)if(heng[i])sum=sum-heng[i]+1;
    for(int j=1;j<=n;j++)if(zong[j])sum=sum-zong[j]+1;
    /*特殊情况*/
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<205;j++)used[j]=false;
        if(mat(i))sum+=heng[i]-1;
    }
    printf("%lld\n",sum);  
}