제목 주소

제이의 가장 큰 차이

제목: nn의 개수를 주고 이 n의 개수 중 두 개의 수의 최대 차이를 찾아라. 제목에 서명하고 마지막 순서를 정렬하고 첫 번째 문제를 줄여라.
AC 코드

#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '
'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
 
 
int a[maxn];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    cout<<a[n-1]-a[0]<<endl;
    return 0;
}

E.A+B 질문

제목: 컴퓨터 프로그래밍 연산에서 i n t int 범위 내의 두 개의 수와 c c c 문제풀이를 찾을 수 있도록 값 c c c c c를 제공합니다: 컴퓨터 연산에서 만약 숫자가 i n t int int가 넘치면 출력의 결과는 여전히 i n t int 내의 수(즉 이 숫자가 넘친 숫자를 제거한 결과)입니다. 따라서 c가 얼마든지 상관없이 각 int 내의 수에 대해모두 하나의 수와 그의 합은 c와 같기 때문에 i n t int 합계 (1l l l < 32) (1ll < 32) (1ll < 32) 개수를 출력하면 된다
AC 코드

#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '
'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=5e3+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cout<<(1ll<<32);
    return 0;
}

I. 꼬치 찾기

제목: 문자열을 주고 최대 사전 순서의 하위 문자열을 찾습니다: O (n 2) O (n ^2) O (n 2) O (n 2) O (n 2) O (n 2) O (n 2) O (n 2) O (n 2) O (n 2)
AC 코드

#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '
'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=5e3+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
 
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    string s;
    cin>>s;
    int n=s.length();
    string ans;
    ans+='a';
    for(int i=0;i<n;i++){
        string t;
        t+=s[i];
        ans=max(ans,t);
        for(int j=i+1;j<n;j++){
            t+=s[j];
            ans=max(ans,t);
        }
    }
    cout<<ans<<endl;
    return 0;
}

B.계단

제목: 정수 ppp를 주고 최소 정수 nn을 구하면 n!  ~n!~  n!p~p~p의 배수문제해: 먼저 질인자를 분해하고 어떤 질인자가 하나가 아니라면 이 인자의 배수를 매거하여 어느 배수의 인자가 이 수보다 큰지 보고 그를 저장한다.만약 질인자가 하나밖에 없다면 바로 저장할 수 있다.그리고 이 수를 최대치로 하는 것이 답이다.
AC 코드

#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '
'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=5e3+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
 
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int p;
        cin>>p;
        map<int,int> m;
        int i;
        for(i=2;i<=sqrt(p);i++){
            while(p%i==0){
                m[i]++;
                p/=i;
            }
        }
        if(p>1)m[p]++;
        int ans=1;
        for(auto i:m){
            int a=i.fi,b=i.se;
            int tmp=0;
            while(b>0){
                tmp+=a;
                int x=tmp;
                while(x%a==0)x/=a,b--;
            }
            ans=max(tmp,ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

G. 나무에서 화해를 구하다

제목: nn개의 점, n-1n-1n-1의 테두리를 포함하는 나무 한 그루가 있는데 각 테두리에 0-n-10~-n-1 0-n-1의 값을 주어 0u∀v∑를 만든다.w ( u , v ) ∀u∀v\sum.w(u,v) ∀u∀v∑.w(u, v)의 최소 w(u, v) w(u, v) w(u, v)는 u에서 v까지의 간단한 경로에서 변수와 문제풀이를 대표한다. n<=1 e 5 n<=1 e5 n<=1 e5 n<=1 e5이기 때문에 폭력적으로 찾을 수 없기 때문에 우리는 각 변수가 계산된 횟수를 각 변수에 대해 분석할 수 있다. 우리는 이 변을 왼쪽 구역과 오른쪽 구역으로 나눌 수 있다. 왜냐하면 두 점 모두 한 번 계산되기 때문에 이 변의 계산 횟수는 바로 왼쪽 포인트에 오른쪽 포인트를 곱한 것이다.그리고 이 값을 정렬하여 횟수가 많은 부소값을 계산한다.그리고 포인트를 계산하는 방법: 먼저 D F S DFS DFS는 결점 1 1 1 1부터 검색하고 각 결점에 대해 그가 얼마나 많은 하위 결점을 가지고 있는지 계산한다.그리고 다시 한 번 DFS DFS DFS로 각 변을 분석합니다. 마찬가지로 결점 111부터 검색을 시작합니다. 그의 자결점에 대응하는 구역의 포인트는 바로 방금 계산한 이 자절점의 포인트입니다.아버지 결점에 대응하는 그 쪽 구역의 점수 n--이 결점의 자결점수(즉 방금 계산한 결점) n-이 자결점의 자결점수(즉 방금 계산한 결점) n--이 자결점의 자결점수(즉 방금 계산한 결점) 그리고 매번 아래로 검색할 때마다 매번 업데이트하는 자결점의 값은 nnn이다.마지막으로 위에서 말한 방법을 찾아 값을 부여하여 계산할 수 있다.
AC 코드

#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '
'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
 
ll dp[maxn];
vector<int> g[maxn];
vector<ll> vec;
void dfs(int u,int fa){
    dp[u]=1;
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u]+=dp[v];
    }
}
void dfs1(int u,int fa){
    for(auto v:g[u]){
        if(v==fa)continue;
        vec.pb((dp[u]-dp[v])*dp[v]);
        dp[v]=dp[u];
        dfs1(v,u);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,0);
    dfs1(1,0);
    ll ans=0;
    sort(all(vec));
    for(ll i=0;i<vec.size();i++){
        ans+=(n-i-1)*vec[i];
    }
    cout<<ans;
    return 0;
}

C. 전체 그림

제목: nn개의 점을 포함하는 완전한 그림을 주고 mm의 변을 삭제하면 최대 몇 개의 연결 분량으로 나눌 수 있다. 먼저 욕심을 부리고 변을 삭제할 때의 가장 큰 상황은 매번 한 점을 삭제하면 독립점이 되고 각 점은 n-1n-1n-1변을 연결한다. 삭제한 후에 이 완전한 그림은 n-3-1n-1n-1의 점을 포함하는 완전한 그림이 된다.그리고 이 조작을 계속 순환하기 때문에 매번 가장자리를 삭제하는 수량은 n-3-1+n-32+.n − i > = m n-1+n-2+......+n-i>=m n−1+n−2+......+n-i>=m 그리고 ii i의 최소값을 찾으면 (i+1)(i+1)(i+1)이 마지막 답입니다. n, m<=1e18n, m<=1e18n, m<=1e18n, m<=1e18 데이터가 상당히 커서 순환할 수 없기 때문에 2점을 사용합니다. 그러나 이런 조작으로 인해 폭발할 수 있습니다.int128 그래서 한 번 사용해서 폭발을 방지할 수 있지만 사실 사용하지 않아도 된다. 왜냐하면 이 값은 m을 겨우 초과했을 뿐이기 때문이다. 그러나 2점의 값이 m에 도달할 수 있도록 확보하고 2점의 오른쪽 경계를 계산하면 된다. 이렇게 하면 lo n g l o n n g n g longlonglonglonglonglonglonglonglonglong만 사용해도 답을 얻을 수 있다.
AC 코드

#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '
'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
 
        ll n,m;
        cin>>n>>m;
        ll l=1,r=n,ans=0;
        while(l<=r)
        {
            __int128 mid=l+r>>1;
            __int128 x=(mid-1)*n-mid*(mid-1)/2;
            if(x<=m) ans=mid,l=mid+1;
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

H. 이상한 가방 문제가 증가했습니다.

제목: 가방의 용량은 2 30 2^ {30} 230 m개수 ki ki ki, m 개 아이템을 대표하며 각 아이템의 부피 c i = 2 k i ci=2^{k i}ci=2ki 적당히 채울 수 있느냐고 묻는다. 적당히 채우려면 어떤 물품으로 풀어야 하느냐고 묻는다. 한 수조로 매번 부족한 부피를 표시한다. 예를 들어 처음에 부족한 것은 3030303030, 303030이 없으면 22개 2929로 303030을 채워야 한다. 그래서 현재 부족한 3030을 0으로 돌리고 29292929의 부족한 수를 +=2*303030의 부족한 수를 2로 미루어 순서가 정해진 물품과 비교한다.만약 이 부피의 물품이 존재한다면 이 물품이 필요하다고 표시한다. 만약 이 물품의 수량이 필요한 수량을 초과하면 모든 필요한 표시를 출력한 후에 답을 출력할 수 있다. 만약에 모든 물품이 마지막에 부족한 부피가 있다면 달성할 수 없다.
AC 코드

#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '
'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int a[maxn],b[maxn],ans[maxn],cnt[40];
bool cmp(int i,int j){
    return a[i]>a[j];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            b[i]=i;
            ans[i]=0;
        }
        sort(b+1,b+1+n,cmp);
        memset(cnt,0,sizeof cnt);
        cnt[30]=1;
        for(int i=1,j=30;i<=n&&j>=0;){
            if(a[b[i]]!=j)cnt[j-1]+=cnt[j]*2,cnt[j]=0,j--;
            else {
                cnt[j]--,ans[b[i]]=1;
                i++;
                if(!cnt[j])break;
            }
        }
        bool f=0;
        for(int i=0;i<=30;i++)if(cnt[i])f=1;
        if(f)cout<<"impossible"<<endl;
        else{
            for(int i=1;i<=n;i++)
                cout<<ans[i];
            cout<<endl;
        }
    }
    return 0;
}

A.막법기록

제목: n∗m n*m n∗m 크기의 격자가 존재하는데 그 중에서 일부 적의 소와 소는 a회 정행제거와 bb회 정열제거를 할 수 있다. 소와 소는 모든 적을 섬멸할 수 있느냐고 묻는다. nn의 범위가 상당히 작기 때문에 2진법으로 제거를 하는 상황을 직접 고려할 수 있다. 행제거한 후에 남은 적들이 필요로 하는 열제거가 b회를 초과하는지 볼 수 있다.
AC 코드

#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '
'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

char g[30][maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n,m,a,b;
        cin>>n>>m>>a>>b;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>g[i][j];
        bool f=0;
        for(int st=0;st<(1<<n);st++){
            if(__builtin_popcount(st)!=a)continue;
            int cnt=0;
            for(int j=0;j<m;j++){
                bool f1=0;
                for(int i=0;i<n;i++)
                    if(!((st>>i)&1)&&g[i][j]=='*')f1=1;
                if(f1==1)cnt++;
            }
            if(cnt<=b){f=1;break;}
        }
        if(f)cout<<"yes";
        else cout<<"no";
        cout<<endl;
    }
    return 0;
}