[Codeforces 1475] Codeforces Round #697(Div.3) | 전체 문제 해결
emm, 소극적이다, 소극적이다.이번엔 ak ak ak 할 수 있어, u n r unr unr 하기 싫은 거 보니까 이상해, 나도 점수 안 받잖아.
경기 후 333분 GG, 10 10 10분 F F F를 넘기면 안 된다.
마이너스 에너지를 전파하지 않고 문제를 풀기 시작했다.
Codeforces Round #697
A.Odd Divisor
제목 대의:
하나의 정수 nnn이 홀수의 인자를 가지고 있는지 아닌지를 판단하다
제목:
물문제지?
2의 멱인지 아닌지만 판단하면 된다. 2의 멱이 아니면 반드시 기수인자가 있을 것이다.
Code:
/*** keep hungry and calm CoolGuang! ***/
#pragma GCC optimize(3)
#include
",x);
#define di(x) printf("%d
",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;while(!isdigit(c)){
if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);
while(n!=1){
if(n%2 == 0) n/=2;
else break;
}
printf("%s
",n==1?"NO":"YES");
}
return 0;
}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/
B.New Year’s Number
제목 대의:
2020 2020 2020 몇 개와 2021 2021 2021 몇 개로 구성될 수 있는지 n의 정수 판단
제목:
명령 x = n/2020 x = n/2020 x = n/2020:
Code:
/*** keep hungry and calm CoolGuang! ***/
#pragma GCC optimize(3)
#include
",x);
#define di(x) printf("%d
",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;while(!isdigit(c)){
if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);
ll temp = n/2020;
if(temp <= 0) printf("NO
");
else{
if(n%2020 <= temp) printf("YES
");
else printf("NO
");
}
}
return 0;
}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/
C.Ball in Berland
제목 대의:
사실 이 문제를 나는 다 읽지 못해서 제목의 뜻을 알아맞혔다.
a,b,(c,d)(a,b),(c,d)(a,b)(a,b),(c,d)로 a!=c , b ! = d a != c,b != d a!=c,b!=d
제목:
명백한 배제 원리:
가령 iii는 앞의 (i-3-1)(i-1)(i-3-1)과 모두 조합한 다음에 요구에 부합되지 않는 것을 줄일 수 있다.
AA집합은 남학생이 같은 집합을 하고 BB는 여학생이 같은 집합을 하는 것을 의미한다. 분명히 요구: A∪ B∪ B∪ B∪
m a p map map을 저장하고 배척 원리를 직접 적용하면 됩니다.
Code:
/*** keep hungry and calm CoolGuang! ***/
#pragma GCC optimize(3)
#include
",x);
#define di(x) printf("%d
",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;while(!isdigit(c)){
if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
map<int,int>A,B;
map<pair<int,int>,int>C;
ll a[maxn],b[maxn];
int main(){
int T;scanf("%d",&T);
while(T--){
ll att,bt;
read(att);read(bt);read(n);
A.clear();B.clear();C.clear();
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) read(b[i]);
ll ans = 0;
for(int i=1;i<=n;i++){
ans += (i-1)*1ll - (A[a[i]]+B[b[i]]-C[{
a[i],b[i]}]);
A[a[i]]++;B[b[i]]++;
C[{
a[i],b[i]}]++;
//debug(ans);
}
dl(ans);
}
return 0;
}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/
D. Cleaning the Phone
제목 대의:
추상: N N 개의 물품을 제시하고 모든 물품은 하나의 품질과 비용이 있으며 품질이 m m m보다 클 때의 최소 비용을 구한다.
제목:
사실 이 문제는 좀 오래 걸렸어요.
제목의 뜻을 잘못 봐서 b i b 를 발견하지 못했습니다.ibi는 두 가지 값만 얻을 수 있다. 두 가지 값만 얻을 수 있기 때문에 최종 상태를 직접 열거할 수 있다. 즉, 첫 번째 값을 얻는 bibibi는 최종 답안에 몇 개가 있을 수 있는지 욕심에 따라 최소 비용을 계산한다.자에서 2점을 뽑아도 되는데, 여기서 채택한 2점.
Code:
/*** keep hungry and calm CoolGuang! ***/
#pragma GCC optimize(3)
#include
",x);
#define di(x) printf("%d
",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;while(!isdigit(c)){
if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
struct node{
ll x,y;
bool friend operator<(node a,node b){
if(a.y == b.y) return a.x > b.x;
return a.y < b.y;
}
}q[maxn];
ll sum[maxn];
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);read(m);
for(int i=1;i<=n;i++) read(q[i].x);
for(int i=1;i<=n;i++) read(q[i].y);
sort(q+1,q+1+n);
int last = 0;
for(int i=1;i<=n;i++){
if(q[i].y == 1) last = i;
sum[i] = sum[i-1] + q[i].x;
}
if(sum[n]<m){
printf("-1
");
continue;
}
ll ans = INF;
for(int i=0;i<=last;i++){
int l = last,r = n;
int tmp = -1;
while(l<=r){
int mid = (l+r)/2;
if(sum[mid]-sum[last] + sum[i] >= m){
r = mid-1;
tmp = mid;
}else l = mid+1;
}
if(tmp!=-1) ans = min(ans,i*1 + (tmp-last)*2ll);
}
printf("%lld
",ans);
}
return 0;
}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/
E. Advertising Agency
제목 대의:
먼저 mx=mx=mx=수조의 길이를 k의 가장 큰 서열과
길이가 kk인 하위 서열의 합이 얼마나 되는지 묻기 = mx=mx=mx
제목:
이 문제는 꽤 많은 방법이 있을 것이다
명령 d p i j dp{ij}dpij는 i번째 숫자로 끝납니다. 길이가 j의 하위 서열의 최대 합입니다.명령 c i j c{ij}cij는 i번째 숫자로 끝납니다. 길이가 j의 하위 서열의 최대 수량입니다.
우선 유추 최단거리 계수의 상태 이동은 다음과 같다.
분명히 3차원 순환이지만 최대값과 관계가 있기 때문에 접두사 최대값과 접두사 최대값의 수량을 한 층 최적화하면 됩니다 fo r for for
Code:
/*** keep hungry and calm CoolGuang! ***/
#pragma GCC optimize(3)
#include
",x);
#define di(x) printf("%d
",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;while(!isdigit(c)){
if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll dp[1005][1005],c[1005][1005];
ll pre[1005],ct[1005];
ll a[maxn];
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);read(m);
for(int i=1;i<=n;i++) read(a[i]);
memset(ct,0,sizeof(ct));
memset(pre,0,sizeof(pre));
for(int i=0;i<=n;i++)
for(int k=0;k<=m;k++)
dp[i][k] = c[i][k] = 0;
c[0][0] = 1;
ct[0] = 1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dp[i][j]<pre[j-1]+a[i]){
dp[i][j] = pre[j-1]+a[i];
c[i][j] = ct[j-1];
}else if(dp[i][j] == pre[j-1]+a[i]) c[i][j] = (c[i][j] + ct[j-1])%mod;
}
for(int j=0;j<=m;j++){
if(pre[j]<dp[i][j]){
ct[j] = c[i][j];
pre[j] = dp[i][j];
}else if(pre[j] == dp[i][j]) ct[j] = (ct[j] + c[i][j])%mod;
}
}
ll ans = 0,mx = 0;
for(int i=1;i<=n;i++) mx = max(mx,dp[i][m]);
//debug(mx);
for(int i=1;i<=n;i++)
if(mx == dp[i][m])
ans = (ans + c[i][m])%mod;
dl(ans);
}
return 0;
}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/
F. Unusual Matrix
제목 대의:
0101 매트릭스, sss와 tt 2개 제시.매번 ss의 한 줄을 옮기거나 tt의 한 줄을 옮기거나 일련의 조작을 통해 ss를 tt로 바꿀 수 있는지 물어볼 수 있다.
제목:
하나의 사유 문제.
(i, j)(i, j)(i, j) 조작의 연관성을 고려할 수 있고, (i, j)(i, j)(i, j) 조작은 (1, j)(1, j)(1, j) 또는 (i, 1)(i, 1)(i, 1)(i, 1)(i, 1)의 값을 바꿀 수 있지만, 이 두 가지는 (1, 1)(1, 1)(1, 1)(1, (1, 1)(1, 1)로 다시 바꿀 수 있다.그래서 이 네 개가 연관조야.다 같거나 다 다를 때는 네 개를 만족시킬 수 없다.
Code:
/*** keep hungry and calm CoolGuang! ***/
#pragma GCC optimize(3)
#include
",x);
#define di(x) printf("%d
",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;while(!isdigit(c)){
if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
char s[maxn];
int c[1005][1005];
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int k=1;k<=n;k++) c[i][k] = s[k]-'0';
}
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int k=1;k<=n;k++) c[i][k] ^= s[k]-'0';
}
int flag = 0;
for(int i=2;i<=n;i++){
for(int k=2;k<=n;k++){
if(c[1][k]^c[i][1]^c[1][1]^c[i][k]) flag = 1;
}
}
printf("%s
",flag?"NO":"YES");
}
return 0;
}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/
G. Strange Beauty
제목 대의:
하나의 그룹을 정의하는 것은 좋습니다. 현재 임의의 두 개의 숫자 i, ji, ji, j가 모두 ai를 만족시킬 뿐입니다.i | a_j ai aj 또는 a j aaj | a_i aj∣ai.
최소한 몇 개의 수를 삭제해서 그룹을 좋아지게 하세요.
제목:
어릴 때부터 대장수 그룹 정렬을 고려(사실 사용하지 않아 이해하기 편함)
명령 d p i dpi dpi의 최대 값은 a i a 입니다.iai가 좋은 그룹의 최대 용량은 얼마입니까
그렇다면 명백하다.
i f ( a k % a i = = 0 ) if(a_k\%a_i==0) if(ak%ai==0) d p [ i ] = d p [ k ] + a i dp[i] = dp[k] + a_i dp[i]=dp[k]+ai의 수량
R e a s o n: Reason: Reason: 최대값은 a k ak ak, a i a_i ai도 ak akak 정제수
그래서 어떤 인자가 있는지 알기만 하면 된다. 체로 한번 쳐볼까?
Code:
/*** keep hungry and calm CoolGuang! ***/
#pragma GCC optimize(3)
#include
",x);
#define di(x) printf("%d
",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;while(!isdigit(c)){
if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll a[maxn];
ll vis[maxn];
ll c[maxn],w[maxn];
ll dp[maxn];
vector<int>v[maxn];
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);
ll mx = 0;
for(int i=1;i<=n;i++){
read(a[i]);
mx = max(mx,a[i]);
vis[a[i]]++;
}
for(int i=1;i<=mx;i++){
v[i].clear();
dp[i] = 0;
}
ll ans = INF;
for(int i=1;i<=mx;i++){
for(int k=2*i;k<=mx;k+=i) v[k].push_back(i);
}
sort(a+1,a+1+n);
//for(int i=1;i<=n;i++) printf("%lld ",a[i]);
for(int i=1;i<=n;i++){
dp[a[i]] = vis[a[i]];
for(int e:v[a[i]]) dp[a[i]] = max(dp[e]+vis[a[i]],dp[a[i]]);
//debug(dp[a[i]]);
int k = i;
ans = min(ans,n-dp[a[i]]);
while(a[k] == a[i] && k<=n) k++;
i = k-1;
}
printf("%lld
",ans);
for(int i=1;i<=n;i++) vis[a[i]]--;
}
return 0;
}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
