练习8

practise

A Kevin7Zz

#include <cstdio>
//#include <iostream>
#include <algorithm>
#include <cstring>
//#include <queue> //priority_queue 优先队列
//#include <map>
//#include <set> //multiset  set<int,greater<int>>大到小
//#include <vector>// ::iterator it;
//#include <stack>
//#include <cmath> // auto &Name : STLName  Name.
//#include <utility>
//#include <sstream>
//#include <string>
#define mod 1000000007
#define mod9 998244353
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;
const db eps=1e-10;
const int INF = 0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=1e3+5;
using namespace std;
int n,m,k=0;
int main(){
    scanf("%d",&n);
    if(n%2) printf("%d\n",2*n);
    else printf("%d\n",n);
    return 0;
}

B Kevin7Zz

#include <cstdio>
//#include <iostream>
#include <algorithm>
#include <cstring>
//#include <queue> //priority_queue 优先队列
//#include <map>
//#include <set> //multiset  set<int,greater<int>>大到小
//#include <vector>// ::iterator it;
//#include <stack>
//#include <cmath> // auto &Name : STLName  Name.
//#include <utility>
//#include <sstream>
//#include <string>
#define mod 1000000007
#define mod9 998244353
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;
const db eps=1e-10;
const int INF = 0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+5;
using namespace std;
int t,n,m,k=0;
int a[N]={0};
int main(){
    scanf("%d",&t);
    for(int j=1;j<=t;j++){
        int sum=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        sort(a+1,a+n+1);
        m=n/3;
        while(m--){
            sum-=a[n-2];
            n-=3;
        }
        printf("Case #%d: %d\n",j,sum);
    }
    return 0;
}

C 6109118071

#include<iostream>
#include<set>
#include<string.h>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
ll n, d, x = 0, k = 2, tp;
void gt(ll num, ll bas)
{
    int sum = 0;
    while (num % bas == d && num > 0)
    {
        sum++;
        num /= bas;
    }
    if (x < sum || x == sum && bas < k)
    {
        x = sum;
        k = bas;
    }
}
signed main(){
    scanf("%lld%lld", &n, &d);
    tp = n - d;
    if (tp >= 0)
    for (int i = 2; i <= sqrt(tp); i++)
    {
        if (tp % i == 0)
        {
            gt(n, i);
            gt(n, tp / i);
        }
    }
    if (tp >= 2)
        gt(n, tp);
    if (n == d && n >= 1)
    {
        x = 1;
        k = n + 1;
    }
    for (int i = 2; i <= 20; i++)   gt(n, i);
    if (n == 0 && d == 0)   x = 1;
    printf("%lld %lld\n", k, x);
}

D 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef double db;
int main(){
    db a,b,c;
    while(cin>>a>>b>>c){
        printf("%.5f\n",a/(a+b)*b/(a+b-c-1)+b/(a+b)*(b-1)/(a+b-c-1));
    }
    return 0;
}

E 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 x,y;
ll n,k;
int check1(ll x){
    x*=2;
    ll s=0,y=1,i;
    for(i=2;i*x<=n;i*=2){
        y*=2;
        s+=y;
        if(s+1>=k) return 1;
    }
    i/=2;
    s+=min(y*2,n-i*x+1);
    if(s+1>=k) return 1;
    else return 0;
}
int check(ll x){
    ll s=0,y=1,i;
    for(i=2;i*x<=n;i*=2){
        y*=2;
        s+=y;
        if(s>=k) return 1;
    }
    i/=2;
    s+=min(y*2,n-i*x+1);
    if(s>=k) return 1;
    else return 0;
}
//1 3 7 15 
//2 4 8 16
int main(){
    cin>>n>>k;
    if(n==k){
        cout<<"1"<<endl;
        return 0;
    }
    if(k==1){
        cout<<n<<endl;
        return 0;
    }
    ll l=1,r=n,m,mm;
    while(l<=r){
        m=(l+r)/2;
        if(m%2) m++;
        if(m==mm) break;
        mm=m;
        if(check(m)){
            l=m;
        }else{
            r=m-1;
        }
    }
    if(check1(m+1)) cout<<m+1<<endl;
    else cout<<m<<endl;
    return 0;
}

F 541907010220

#include<iostream>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define me(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=1111122;
const int M=200005;
int a[N],v[N];
int main()
{
    int m,i,j,n,k,r,l,maxx=0,s=0,r1,l1;
    cin>>n>>k;
    me(v,0);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    r=1;l=1;
    while(1)
    {
        if(r>n)break;
        while(s<k)
        {
            if(!v[a[r]])
            {
                s++;
                v[a[r]]++;
                r++;
            }
            else 
            {
                v[a[r]]++;
                r++;
            }
            if(r>n)break;
        }
        if(maxx<r-l)
        {
            maxx=r-l;
            l1=l;
            r1=r-1;
        }
        if(r>n)break;
        if(s>=k)
        {
            if(v[a[r]]>0)
            {
                v[a[r]]++;
                r++;
                if(maxx<r-l)
               {
            maxx=r-l;
            l1=l;
            r1=r-1;
                }
            }
            else 
            {
                if(v[a[l]]>1)
            {
                v[a[l]]--;
                l++;
            }
            else if(v[a[l]]==1)
            {
                s--;
                v[a[l]]--;
                l++;
            }
            }
        }
    }
    cout<<l1<<" "<<r1<<endl;
    return 0;
}

G 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
int n,m,vis[100010],x,y,z;
vector<int> g[100010];
void dfs(int now){
    vis[now]=1;
    for(auto to:g[now]){
        if(!vis[to]){
            dfs(to);
        }
    }
    return ;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            ans++;
            dfs(i);
        }
    }
    printf("%d\n",ans);
    return 0;
}

H 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
int n,m,u,v;
vector<int> g[200010];
int edg[200010][2],vis[200010],cr[200010];
void dfs(int now,int color){
    vis[now]=1;
    cr[now]=color;
    for(auto to:g[now]){
        if(!vis[to]){
            dfs(to,1-color);
        }
    }
}
vector<int> ans;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        g[v].push_back(u);
        g[u].push_back(v);
        edg[i][0]=u;edg[i][1]=v;
    }
    dfs(1,0);
    for(int i=1;i<=m;i++){
        if(cr[edg[i][0]]==cr[edg[i][1]]){
            puts("NO");
            return 0;
        }
        ans.push_back(cr[edg[i][0]]);
    }
    puts("YES");
    for(auto to:ans){
        printf("%d",to);
    }putchar('\n');
    return 0;
}

I 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const ll mod=1e9+7;
ll n,a[300010],ans;
ll cnt[2][64],p,sv[64],pow2[64];
int main(){
    cin>>n;
    pow2[0]=1;
    for(int i=1;i<=62;i++){
        pow2[i]=2ll*pow2[i-1]%mod;
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=n;i>=1;i--){
        p=0;memset(sv,0,sizeof(sv));
        while(a[i]){
            sv[++p]=a[i]%2ll;
            a[i]/=2ll;
        }
        for(int i=1;i<=62;i++){
            ans=(ans+pow2[i-1]*cnt[1-sv[i]][i]%mod)%mod;
        }
        for(int i=1;i<=62;i++){
            cnt[sv[i]][i]++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}