2012 ACM/ICPC Asia Regional Online Warmup部分コードとデータ
まとめて見ますhttp://blog.csdn.net/woshi250hua/article/details/7908090
1002コード:
1002コード:
#include <stdio.h>
#include <string.h>
#define MAX 1110000
#define int64 __int64//long long
struct point{
int64 y,x;
}pot[MAX];
int n,m,arr[MAX];
int qu[MAX],head,tail;
int64 sum[MAX],dp[MAX];
int CheckIt(int x,int y,int z) {
point p0 = pot[x],p1 = pot[y],p2 = pot[z];
return (p0.x - p1.x) * (p0.y - p2.y) - (p0.y - p1.y) * (p0.x - p2.x) < 0;
}
int NotBest(int x,int y,int k) {
point p0 = pot[x],p1 = pot[y];
//printf("%lld,%lld %lld,%lld
",p0.x,p0.y,pot[1].x,p1.y);
return p0.y - k * p0.x > p1.y - k * p1.x;
}
int GetInt() {
char ch = ' ';
while (ch < '0' || ch > '9')
ch = getchar();
int x = 0;
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0',ch = getchar();
return x;
}
int64 Solve_DP() {
int i,j,k;
head = 0,tail = 0;
//pot[0].x = sum[1],pot[0].y = sum[1] * sum[1];
for (i = 1; i <= n; ++i) {
pot[i].x = sum[i];
pot[i].y = dp[i-1] + sum[i] * sum[i];
while (head <= tail - 1
&& CheckIt(qu[tail-1],qu[tail],i)) tail--;
qu[++tail] = i;
while (head + 1 <= tail
&& NotBest(qu[head],qu[head+1],2 * sum[i])) head++;
k = qu[head];
dp[i] = pot[k].y - 2 * sum[i] * pot[k].x + m + sum[i] * sum[i];
}
return dp[n];
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m),n+m) {
for (i = 1; i <= n; ++i)
sum[i] = GetInt();//scanf("%d",&sum[i]);
int64 ans = Solve_DP();
printf("%I64d
",ans);
}
}#include <stdio.h>
#include <string.h>
#define MAX 10000
#define int64 __int64
int used[MAX],n,m;
int sum[MAX],col[MAX];
int64 Gcd(int64 x,int64 y) {
int r = x % y;
while (r) {
x = y,y = r;
r = x % y;
}
return y;
}
int64 Lcm(int64 x,int64 y) {
return x / Gcd(x,y) * y;
}
int Cal(int x) {
int i,j,k,cnt;
cnt = used[x] = 1;
i = (x + m - 1) / m;
j = x % m ? x % m : m;
k = sum[j-1] + (col[j] - i + 1);
//printf("%d
",k);
while (!used[k]) {
used[k] = 1;
cnt++;
i = (k + m - 1) / m;
j = k % m ? k % m : m;
k = sum[j-1] + (col[j] - i + 1);
}
return cnt;
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m),n + m) {
memset(used,0,sizeof(used));
int64 ans = 1;
for (i = 1; i <= m; ++i) {
col[i] = n / m;
if (i <= n % m) col[i]++;
sum[i] = sum[i-1] + col[i];
}
for (i = 1; i <= n; ++i)
if (!used[i]) {
int64 tp = Cal(i);
ans = Lcm(ans,tp);
}
printf("%I64d
",ans);
}
}#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 2100
#define INF (1<<30)
#define min(a,b) ((a)<(b)?(a):(b))
int n,m,arr[MAX];
int dp[MAX][MAX];
int cost[MAX][MAX];
priority_queue<int> high;
priority_queue<int,vector<int>,greater<int> > low;
void Calculate(int beg) {
int i,j,k,tp;
int sumlow = 0,sumhigh = 0;
cost[beg][beg] = 0;
if (arr[beg] > arr[beg + 1]) {
low.push(arr[beg]);
high.push(arr[beg+1]);
}
else {
low.push(arr[beg+1]);
high.push(arr[beg]);
}
cost[beg][beg+1] = low.top() - high.top();
sumlow += low.top(),sumhigh += high.top();
for (i = beg + 2; i <= n; ++i) {
if (arr[i] >= high.top()) {
low.push(arr[i]);
sumlow += arr[i];
}
else {
high.push(arr[i]);
sumhigh += arr[i];
}
int hsize = high.size(),lsize = low.size();
int htop = high.top(),ltop = low.top();
if (hsize - lsize == 2) {
sumlow += htop;
sumhigh -= htop;
lsize++,hsize--;
low.push(htop),high.pop();
}
else if (low.size() - high.size() == 2) {
sumlow -= ltop;
sumhigh += ltop;
lsize--,hsize++;
high.push(ltop),low.pop();
}
if (lsize >= hsize) tp = low.top();
else tp = high.top();
cost[beg][i] = sumlow - tp * lsize;
cost[beg][i] = cost[beg][i] + tp * hsize - sumhigh;
//printf("%d,%d low%d high%d pt %d cost%lld
",beg,i,low.size(),high.size(),tp,cost[beg][i]);
}
}
void Initial() {
int i,j,k;
for (i = 1; i < n; ++i) {
while (!low.empty()) low.pop();
while (!high.empty()) high.pop();
Calculate(i);
}
for (i = 0; i <= n; ++i)
for (j = 0; j <= m; ++j)
dp[i][j] = INF;
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m),n) {
for (i = 1; i <= n; ++i)
scanf("%d",&arr[i]);
Initial();
dp[0][0] = 0;
for (j = 0; j < m; ++j)
for (k = 0; k < n; ++k)
if (dp[k][j] != INF)
for (i = k + 1; i <= n ; ++i)
dp[i][j+1] = min(dp[i][j+1],dp[k][j]+cost[k+1][i]);
printf("%d
",dp[n][m]);
}
}
/*
7 2
6 5 4 3 2 1 7
5 5
5 5 5 5 5
5 2
-5 -4 -3 -2 -1
7 3
6 5 4 3 2 1 7
*/#include <stdio.h>
#include <string.h>
#define MIN 1100
#define MAX 1000000
struct node {
int v,kind;
node *next;
}tree[MAX*2],*head[MIN];
int ptr,n,m,k,flag;
int fa[MIN],rank[MIN];
void Initial() {
ptr = flag = 0;
memset(head,NULL,sizeof(head));
for (int i = 1; i <= n; ++i)
fa[i] = i,rank[i] = 1;
}
void AddEdge(int x,int y,int kind) {
tree[ptr].v = y,tree[ptr].kind = kind;
tree[ptr].next = head[x],head[x] = &tree[ptr++];
}
int Getfa(int x) {
int r = x,q;
while (r != fa[r]) r = fa[r];
while (r != x) {
q = fa[x];
fa[x] = r;
x = q;
}
return r;
}
int Solve() {
int i,j;
int mmax = 0,mmin = 0;
node *p;
for (i = 1; i <= n; ++i) {
p = head[i];
while (p != NULL) {
if (p->kind) {
int u = i,v = p->v;
int ta = Getfa(u),tb = Getfa(v);
if (ta != tb)
fa[ta] = tb,mmax++;
}
p = p->next;
}
}
for (i = 1; i <= n; ++i)
fa[i] = i,rank[i] = 1;
for (i = 1; i <= n; ++i) {
p = head[i];
while (p != NULL) {
if (p->kind == 0) {
int u = i,v = p->v;
int ta = Getfa(u),tb = Getfa(v);
if (ta != tb)
fa[ta] = tb,mmin++;
}
p = p->next;
}
}
mmin = n - 1 - mmin;
//printf("%d %d
",mmin,mmax);
if (mmin <= k && mmax >= k) return 1;
else return 0;
}
int main()
{
int i,j;
while (scanf("%d%d%d",&n,&m,&k),n+m+k) {
Initial();
for (i = 1; i <= m; ++i) {
int b,c;
char s[2];
scanf("%s %d%d",s,&b,&c);
AddEdge(b,c,s[0]=='B');
AddEdge(c,b,s[0]=='B');
}
int flag = Solve();
printf("%d
",flag);
}
}