\# 개인전 첫 번 째 문제 풀이 총화\#

매번 시합 이 끝 날 때마다 반드시 블 로 그 를 정리 하 는 것 은 습관 이 되 었 다. 경기 에서 파악 해 야 할 것 에 대한 회고 이자 기반 을 다 지 는 동시에 자신의 일부 지식 을 파악 하고 운용 해 야 하지만 완전히 파악 하지 못 한 결함 을 보완 하고 전진 하도록 격려 할 수 있다.Qzone 을 떠 올 리 면 뒤에서 묵묵히 지원 하 는 무언 가 를 기억 할 수 있 는 곳 이기 때문에 요 며칠 동안 총 결 이 계속 업데이트 되 었 습 니 다.경기 링크:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=71326#overview 제목: 복주대학 oj:http://acm.fzu.edu.cn/  A. - 대왕 께 서 순 산 하 라 고 하 셨 어 요.
Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status Practice FZU 2167
Description
대사 형 은 진경 을 얻 은 후에 매일 경 서 를 자세히 읽 고 독서 노트 를 열심히 완성 하 며 이론 과 실제 관 계 를 맺 고 실천 능력 을 계속 향상 시킨다.만약 에 대사 형 이 수련 을 시작 한 첫날 이 월요일 이 고 지금까지 N 일 을 수련 했다 고 가정 하면 얼마나 많은 날 이 토요일 이나 일요일 이 고 대사 형 은 아직도 수련 을 하고 있 습 니까?
Input
각 그룹의 입력 데 이 터 는 하나의 정수 N (0 < N < 100, 000) 을 포함한다.
Output
각 그룹 에 데 이 터 를 입력 하고 한 줄 을 출력 하 며 하나의 정수 만 포함 하여 N 일 중 토요일 이나 일요일 의 일 수 를 표시 합 니 다.
Sample Input
567121314
Sample Output 0 1 2 2 3 4  생각: 물 문제, 설명 안 해 ~ ~
코드:

<span style="font-size:14px;"> #include <iostream>
#include <stdio.h>
 using namespace std;
 int main()
 {
int n,b;
while(cin>>n)
{
b=n/7*2;
if(n%7==6)
  b++;
cout<<b<<endl; 
} return 0;}</span>

B - 방어 진지 I
Crawling in process... Crawling failed Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status Practice FZU 2168
Description
부대 에는 모두 N 명의 병사 가 있 고 모든 병사 들 은 각자 의 능력 지수 인 Xi 를 가지 고 있다. 한 번 의 훈련 에서 지휘 부 는 M 개의 수비 가 필요 한 장 소 를 확정 했다. 중요 도 에 따라 낮은 것 에서 높 은 것 으로 순 서 를 매기 고 숫자 1 에서 M 으로 각 장소의 중요 도 를 표시 했다. 지휘 부 는 M 개 사병 을 선택 하여 순서대로 지 정 된 장소 에 들 어가 수비 임 무 를 수행 할 것 이다.능력 지수 가 X 인 병사 의 수비 중요 도가 Y 인 지점 은 X * Y 의 참고 지 수 를 받 게 된다.현재 병사 들 이 일렬 로 서 있 습 니 다. 연속 적 인 M 개 병 사 를 선택 하여 순서대로 수비 에 참가 하여 전체 참고 지수 가 가장 큽 니 다.
Input
여러 그룹 을 포함 하 는 데 이 터 를 입력 하 십시오.
첫 번 째 줄 에 두 개의 정수 N, M (1 & lt; = N & gt; = 1000000, 1 & lt; = M & gt; = 1000) 을 입력 하고, 두 번 째 줄 의 N 개 정 수 는 병사 마다 대응 하 는 능력 지수 Xi (1 & gt; = Xi & gt; = 1000) 를 나타 낸다.
30% 에 대한 데이터 1 & lt; = M & gt; = N & gt; = 1000.
Output
하나의 정 수 를 출력 하여 가장 큰 참고 지수 총화 이다.
Sample Input
5 3 2 1 3 1 4
Sample Output  17. 사고: 문 제 를 보 자마자 첫 번 째 느낌 으로 폭력 적 으로 순환 해 볼 수 있 습 니 다. 그리고 문 제 를 몇 번 열심히 읽 고 문 제 를 두 드 리 기 시 작 했 습 니 다. 두 드 리 면서 생각 이 없 음 을 발 견 했 습 니 다.멘 붕   물 을 한 모금 마 셨 다. :  a+b+c+d+e    sum[5]
b+c+d+e      sum[5]-sum[1]
sum [n] 으로 전 n 항 과, s [n] 로 전 n 개의 sum 과
얻다
a+2b+3c+4d+5e = 5*sum[5]-(sum[2]+sum[3]+sum[4])
= 5*sum[5] - (s[2]-s[1]+s[3]-s[2]+s[4]-s[3])
= 5*sum[5] - (s[4]-s[2])
 
유도 할 수 있다
ans = m * sum [i] - (s [i - 1] - s [i - 1 - m]) 당연히 뒤에서 앞으로 밀 수 있다.
dp[k]=dp[k-1]-ans[k-1]+x[i]*m;
ans [k - 1] 는 m 개의 수 를 합 친 것 이다. 
(자신 이 신 마 를 말 하고 있 는 지 ~) 물론 일시 적 으로 완전히 이해 할 수 없 는 매우 정상 적 인 문제 입 니 다. 이 문 제 는 zj 도 마지막 에 풀 었 습 니 다.천천히 이해 ~ ~ 코드:

<span style="font-size:14px;">#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <stack>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define Max(a,b) a>b?a:b
using namespace std;
const int N= 1000005;
int aa[N],bb[N];
int main()
{
    int n,m,a,b,i,j,k;
    while(~scanf("%d%d",&n,&m))
    {
        int ans=0,cnt=0;
        aa[0]=bb[0]=0;
        for(i=1; i<=n; i++)
        {
            scanf("%d",&a);
            aa[i]=aa[i-1]+a; //bb[i]=bb[i-1]+a;
            bb[i]=bb[i-1]+aa[i];
        }
        for(i=m; i<=n; i++)
        {
            ans=m*aa[i]-(bb[i-1]-bb[i-1-m]);
            cnt= Max(cnt,ans);
        }
        printf("%d
",n<=m?aa[n]:cnt);
    }
    return 0;
}
</span>

C - shadow
Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status Practice FZU 2169
Description
YL 은 shadow 국 의 왕 이 고 shadow 국 가 는 N 개 도시 입 니 다.비용 을 절약 하기 위해 shadow 국 은 N - 1 개의 도로 만 있 고 이 N - 1 개의 도 로 는 N 개의 도 시 를 연결 시 킵 니 다.어느 해 그림자 나라 에 반란 이 일 어 났 고 반군 이 여러 도 시 를 점령 했 으 며 왕 은 위 태 롭 습 니 다.왕도 가 일련 번호 1 인 도 시 는 왕도 외 에 K 개 도시 에 YL 의 군대 가 있다.이제 이 K 군 대 는 왕 도 를 향 해 진군 하고 지나 가 는 도시 의 반군 을 처치 해 야 한다.N 개 도시 의 도로 상황 과 도시 의 반란군 수 를 알려 드 리 겠 습 니 다. 반란군 을 모두 얼마나 처치 해 야 하 느 냐 고요?
Input
첫 줄 에 정수 N, K 두 개 를 입력 하고, 그 다음 에 N (1 & lt; = N & gt; = 100000) 개의 정수 Ai (0 & gt; = Ai & gt; = 10000) 를 입력 하면 i 번 째 도시 의 반군 수 를 나타 낸다.다음은 K 개 를 1 보다 크 고 N 보다 작은 정수 로 입력 해 군대 가 있 는 도시 의 번 호 를 표시 한다.데이터 보증 왕도 와 군대 가 있 는 도시 에는 반군 이 없다.다음은 N - 1 줄 을 입력 하고 줄 마다 두 개의 정수 u, v 를 입력 하여 u 와 v 를 연결 하 는 길 을 표시 합 니 다.모든 군 대 는 길 을 따라 만 갈 수 있 고 그 도시 와 왕도 사이 의 가장 짧 은 노선 이다.
Output
한 줄 한 줄 을 출력 하면 소 멸 된 반란군 의 수 를 나타 낸다.
Sample Input
4 20 3 0 03 41 22 32 4
Sample Output 3
사고: 또 슬 픈 최 단 로 문제 (디 제 스 트 라, 프로 이 드, SPFA?) 입 니 다. 물론 이 문 제 는 도시 와 도시 의 거 리 를 알려 주지 않 았 습 니 다. (사실 필요 도 없습니다) 미리 처리 할 수 있 습 니 다. 반군 의 수 를 없 애고 각 도시 가 기록 한 반군 의 수 를 처리 하 는 것 을 요구 하기 때 문 입 니 다. ,템 플 릿 을 찍 지 않 았 습 니 다. 자신 은 천천히 기억 에 의 해 조금씩 두 드 리 고 있 습 니 다. 그리고 컴 파일 을 하면 각종 오류 알림!어 쩔 수 없 이 시간 이 제한 되 어 있다. 비록 지 나 쳤 지만 실패했다 (템 플 릿 을 보고)...우선 대기 열 로 최적화 (중요 합 니 다. 시간 초과 방지!) 반군 의 도시 개수, 표 지 를 계산 합 니 다. 반란군 을 처치 하면 모두 처치 할 때 까지 감소 합 니 다: 코드:

<span style="font-size:14px;">#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <stack>
#include <stdio.h>
#include <ctype.h
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
const double eps = 1e-6;
const double Pi = acos(-1.0);
static const int Inf= ~0U>>2;
static const int maxn=111000;
int n,m,N,K,M,ss,i,j;
int mapp[maxn];
int liter[maxn];
int result[maxn];
bool vis[maxn];
int head[maxn];
struct node
{
    int va;
    int na;
}
city[maxn*2];
struct node2
{
    int va2;
    int shadi;
} p, q;
void add(int u, int v)
{
    city[ss].va=v;
    city[ss].na = head[u];
    head[u] = ss++;
}
int dijkstra(int x)
{
    int cnt = 0;
    queue<node2> Q;
    p.va2 = x;
    p.shadi = liter[x];
    Q.push(p);
    vis[x] = 1;
    while (!Q.empty())
    {
        p = Q.front();
        Q.pop();
        if (1 == p.va2) cnt = p.shadi;
        for (int i = head[p.va2]; i != 0; i = city[i].na)
        {
            int v = city[i].va;
            if(vis[v]==0)
            {
                vis[v] = 1;
                q.va2 = v;
                q.shadi = p.shadi + liter[v];
                Q.push(q);
            }
        }
    }
    return cnt;
}
int main()
{
   
    while (cin>>N>>K)
    {
        for (i = 1; i <= N; i++)
            cin>>liter[i];
        for (i = 1; i <= K; i++)
            cin>>result[i];
        mem(vis,0),mem(head,0);
        ss=1;
        int P=N-1;
        for(i=1; i<=P; i++)
        {
            int u,v;
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        int sum = 0;
        for(i=1; i<=K; i++)
        {
            int aa=result[i];
            if (vis[aa]==0)
                sum+=dijkstra(aa);
        }
        printf("%d
",sum);
    }
    return 0;
}

PS：          ，       ，                ，
        ！！  ，                ，  ！</span>

when you wan to give up ,think of why you are persit until now!