Codeforces Round #142 Div.2 문제 해결

A

B

C

D

E

A n , xi, yi, s.
.
. 탐욕스럽게 공격력이 가장 적은 용을 칠 때마다 용을 정렬할 수 있다.

#include //Ithea Myse Valgulious
using namespace std;
const int yuzu=1e5;
struct drn{
int x,y;
bool operator const drn &b) const{
  return x^b.x?xb.y;
  }
}d[yuzu|10];
int main(){
int s=read(),n=read(),i;
for (i=1;i<=n;++i) d[i].x=read(),d[i].y=read();
sort(d+1,d+n+1);
for (i=1;i<=n;++i){
  if (s<=d[i].x) return puts("NO"),0;
  s+=d[i].y;
  }puts("YES");
}

B 3 . 이 수는 분명히 질수의 제곱이어야 한다.체법으로 106 106 이내의 질수를 체로 쳐서 n------√n을 계산하여 판단한다.

#include //Ithea Myse Valgulious
using namespace std;
const int yuzu=1e6;
typedef int fuko[yuzu|10];
fuko pr,p;

void preprime(){
int i,j;
fill(p+2,p+yuzu+10,1);
for (i=2;i*i<=yuzu;++i){
  if (p[i]){
    for (j=i*i;j<=yuzu;j+=i) p[j]=0;
    }
  }
}

bool judge(ll x){
ll t=sqrt(x);
if (t*t^x) return 0;
return p[t];
}

int main(){
preprime();
for (int t=read();t--;){
  ll x;read(x);
  puts(judge(x)?"YES":"NO");
  }
}

C n m 01 , , .
1 , -1. 줄마다 set으로 11의 위치를 저장하고 한 번에 한 열을 열거하며 줄의 2분은 이 열에서 가장 가까운 두 개의 11의 위치를 찾아 이동 횟수에 최소값을 더한다.중간에 WA가 9발을 보냈는데 그 수안 함수는 엉망진창으로 바뀌었지만 결국 A가 떨어졌다.

#include //Ithea Myse Valgulious
using namespace std;
const int yuzu=1e4,_=105,inf=yuzu*_;
typedef int fuko[yuzu|10];
char c[yuzu|10];
set<int> s[_];
int n,m;
#define cal(a,b) min(min(abs(a-b),abs(a+m-b)),abs(b+m-a))//  a     b        .
int suan(int r,int c){
int ans;
auto p=s[r].lower_bound(c);
if (p==s[r].end()){
  ans=min(cal(*s[r].rbegin(),c),cal(*s[r].begin(),c));
  }else if (p==s[r].begin()){
  ans=min(cal(*p,c),cal(*s[r].rbegin(),c));
  }else{
  ans=min(cal(*p,c),cal(c,*--s[r].lower_bound(c)));
  }
return ans;
}

int main(){
int i,j,ans=inf;
scanf("%d%d",&n,&m);
for (i=1;i<=n;++i){
  scanf("%s",c+1);
  for (j=1;j<=m;++j) if (c[j]&1) s[i].insert(j);
  }
for (j=1;j<=m;++j){
  int tmp=0;
  for (i=1;i<=n;++i){
    if (s[i].empty()) return puts("-1"),0;
    tmp+=suan(i,j);
    }
  ans=min(ans,tmp);
  }write(ans);
}

D . i tourist ,
. spfas p f a 뛰면 돼.여기 spfa s p f a 안 죽었어.팀의 우두머리를 꺼낼 때 현재 지점이 dist[i] d i s t[i]에 있는 시간이 어떤tourist에 의해 차지되었는지 확인하고, 그렇지 않으면 dist[i]+1d i s t[i] + 1을 차지하지 않을 때까지 봅시다.이게 다 D문제야. 나 진짜 탄복했어.하지만 나도 T66개의 점이 있다. 그것은 정말 흑역사이다. 나는 매번 한 점까지 확장할 때마다 이 점이 점거되어 T가 날아갔는지 아닌지를 판단한다.

#pragma GCC optimize("inline",3)
#include //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int yuzu=2e5,inf=0x3f3f3f3f;
typedef int fuko[yuzu|10];
struct edge{int to,w;};
vector lj[yuzu|10];
set<int> tors[yuzu|10];
fuko vis,dist;
int n,m;
#define key(v) for (;v^n&&tors[v].count(dist[v]);++dist[v])
int spfa(int s){
queue<int> q;
memset(vis,0,sizeof vis);
memset(dist,0x3f,sizeof dist);
q.push(s),vis[s]=1,dist[s]=0;
for (;!q.empty();){
  int u=q.front();q.pop();
  vis[u]=0;
  key(u);
  for (auto i:lj[u]){
    int v=i.to,w=i.w;
    if (dist[v]>dist[u]+w){
      dist[v]=dist[u]+w;    
      if (!vis[v]) vis[v]=1,q.push(v);
      }
    }
  }
}

int main(){
int i,j;n=read(),m=read();
for (i=1;i<=m;++i){
  int u=read(),v=read(),w=read();
  lj[u].push_back(edge{v,w});
  lj[v].push_back(edge{u,w});
  }
for (i=1;i<=n;++i){
  for (j=read();j--;){
    tors[i].insert(read());
    }
  }
spfa(1);
write(dist[n]^inf?dist[n]:-1);
}

E , m , m .E문제에 이런 문제가 있으니 정말 그녀를 설득시켰다.너는 함부로 하기만 하면 영문도 모른 채 A를 떨어뜨릴 수 있다.영점 i i의 도수는 cnt[i]cnt[i]이고, 파괴된 삼원환의 수는 (n-3-1-3cnt[i])×cnt[i] ( n − 1 − c n t [ i ] ) × c n t [ i ] . 삼원환을 파괴하는 것은 양방향이기 때문에 2로 나누면 된다.

#pragma GCC optimize("inline",3)
#include //Ithea Myse Valgulious
using namespace std;
const int yuzu=1e6;
typedef ll fuko[yuzu|10];
fuko cnt;
int main(){
int n=read(),m=read(),i;
ll ans=0;
for (i=1;i<=m;++i) ++cnt[read()],++cnt[read()];
for (i=1;i<=n;++i) ans+=(n-cnt[i]-1)*cnt[i];
write(1ll*n*(n-1)*(n-2)/6-ans/2);
}

감사합니다.