# Codeforces Round #374 (div.2)遗憾题合集

C.Journey

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-6;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
{
char c = getchar();
x = 0;
while(!isdigit(c)) c = getchar();
while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }
}

const int INF=0x7fffffff;
const int maxn=5010;
int dp[maxn][maxn];
struct Edge
{
int v,nx; int w;
}e[maxn];
int h[maxn],sz,r[maxn];
int n,m,T;
queue<int>Q;
int pre[maxn][maxn];

{
e[sz].v=v; e[sz].w=w;
e[sz].nx=h[u]; h[u]=sz++;
}

int main()
{
scanf("%d%d%d",&n,&m,&T);

for(int i=0;i<=n;i++)
{
h[i]=-1;
for(int j=0;j<=n;j++)
{
dp[i][j]=INF;
pre[i][j]=-1;
}
}

for(int i=1;i<=m;i++)
{
int u,v; LL w; scanf("%d%d%d",&u,&v,&w);
}

dp[1][1]=0;
for(int i=1;i<=n;i++) if(r[i]==0) Q.push(i);
bool flag=0;
while(!Q.empty())
{
int top=Q.front(); Q.pop();
if(top==1) flag=1;
if(flag==0)
{
for(int i=h[top];i!=-1;i=e[i].nx)
{
int to=e[i].v;
r[to]--;
if(r[to]==0) Q.push(to);
}
continue;
}
for(int i=h[top];i!=-1;i=e[i].nx)
{
int to=e[i].v;
for(int j=1;j<=n;j++)
{
if(dp[top][j-1]==INF) continue;
if(dp[top][j-1]+e[i].w>T) continue;
if(dp[top][j-1]+e[i].w>=dp[to][j]) continue;

pre[to][j]=(top-1)*n+j-1-1;
dp[to][j]=dp[top][j-1]+e[i].w;
}
r[to]--;
if(r[to]==0) Q.push(to);
}
}

int sum;
for(int i=1;i<=n;i++) if(dp[n][i]<=T) sum=i;

cout<<sum<<endl;
int nowx=n,nowy=sum; stack<int>S;
while(1)
{
S.push(nowx);
int tx,ty;
tx=pre[nowx][nowy]/n; tx++;
ty=pre[nowx][nowy]%n; ty++;
if(pre[nowx][nowy]==-1) break;
nowx=tx; nowy=ty;
}
while(!S.empty())
{
cout<<S.top()<<" "; S.pop();
}

return 0;
}

D.Maxim and Array

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <queue>
#include <math.h>
using namespace std;

const int N = 200000 + 50;
typedef long long ll;

ll aabs(ll x) {return x<0 ? -x : x;}

struct node
{
ll num;
int id;
bool operator < (const node & temp) const
{
return aabs(num) > aabs(temp.num);
}
};

ll a[N];
ll n,k,x;

int main()
{
cin >> n >> k >> x;
int sign = 1;
priority_queue<node> Q;
for(int i=1;i<=n;i++)
{
scanf("%I64d",a+i);
if(a[i] < 0) sign = -sign;
Q.push((node){a[i],i});
}
while(k--)
{
node temp = Q.top();Q.pop();
if(a[temp.id] < 0)
{
if(sign == -1) a[temp.id] -= x;
else a[temp.id] += x;
if(a[temp.id] >= 0) sign = -sign;
}
else
{
if(sign == -1) a[temp.id] += x;
else a[temp.id] -= x;
if(a[temp.id] < 0) sign = -sign;
}
Q.push((node){a[temp.id],temp.id});
}
for(int i=1;i<=n;i++)
{
printf("%I64d%c",a[i],i==n?‘\n‘:‘ ‘);
}
}

## Codeforces Round #257 (Div. 2) E题：Jzzhu and Apples 模拟

E. Jzzhu and Apples time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Jzzhu has picked n apples from his big apple tree. All the apples are numbered from 1 to n. Now he wants to sell them to

## Codeforces Round #243 (Div. 1) A题

http://codeforces.com/contest/425/problem/A 题目链接: 然后拿出这道题目是很多人不会分析题目,被题目吓坏了,其中包括我自己,想出复杂度,一下就出了啊!真是弱! 直接暴力求出矩阵数值,然后枚举每一个[I,J];再O[N]判断,分配好在[I,J]区间的数和之内的数,再排序下SOLO了 CODE:#include <cstdio> #include <cstring>#include <queue>#include <vect

## Codeforces Round #634 (Div. 3) 补题

A. Candies and Two Sisters 签到题,直接输出即可 代码 #include<bits/stdc++.h> #define INF 0x3f3f3f3f typedef long long ll; using namespace std; inline void read(int &p) { p=0;int flag=1;char c=getchar(); while(!isdigit(c)) {if(c=='-') flag=-1;c=getchar();} w

## Codeforces Round #396 (Div. 2) D题Mahmoud and a Dictionary（并查集）解题报告

Mahmoud wants to write a new dictionary that contains n words and relations between them. There are two types of relations: synonymy (i. e. the two words mean the same) and antonymy (i. e. the two words mean the opposite). From time to time he discov

## Codeforces Round #419 (Div. 1) 补题 CF 815 A-E

A-C传送门 D Karen and Cards 技巧性很强的一道二分优化题 题意很简单 给定n个三元组,和三个维度的上限,问存在多少三元组,使得对于给定的n个三元组中的每一个,必有两个维度严格小于. 首先我们根据一个维度(c维)对n个三元组排序,然后枚举答案在这个维度的取值. 此时序列被分成了两个部分,前半部分 满足所有c大于等于i 后半部分满足所有c严格小于i(即已有一个维度小于) 通过累计,我们知道此时前半部a维的最大值ma和b维的最大值mb. 显然可能存在的三元组答案,必然首先满足a维和

## 【Codeforces】Codeforces Round #374 (Div. 2) -- C. Journey （DP）

C. Journey time limit per test3 seconds memory limit per test256 megabytes inputstandard input outputstandard output Recently Irina arrived to one of the most famous cities of Berland — the Berlatov city. There are n showplaces in the city, numbered