自己太水了。。。呵呵
A題 打表。。。
#include<iostream>
using namespace std;
/**//*
int dp[10000001];
int rex[10000];
int rey[10000];
int main()
{
freopen("out.txt","w",stdin);
int cnt=0;
int i,j;
for(i=1;i<=10000000;++i)
for(j=i<<1;j<=10000000;j+=i)
dp[j] += i;
for(i=220;i<=10000000;++i)
{
if(dp[i]<=10000000&&dp[dp[i]]<=10000000&&i==dp[dp[i]]&&i<dp[i])
{
cnt++;
printf("%d,%d,",i,dp[i]);
}
}
return 0;
}
*/
int dp[200][2]=
{220,284,1184,1210,2620,2924,5020,5564,6232,6368,10744,10856,12285,14595,17296,18416,63020,76084,66928,66992,67095,71145,69615,87633,79750,88730,100485,124155,
122265,139815,122368,123152,141664,153176,142310,168730,171856,176336,176272,180848,185368,203432,196724,202444,280540,365084,308620,389924,319550,430402,356408,
399592,437456,455344,469028,486178,503056,514736,522405,525915,600392,669688,
609928,686072,624184,691256,635624,712216,643336,652664,667964,783556,726104,796696,
802725,863835,879712,901424,898216,980984,947835,1125765,998104,1043096,1077890,
1099390,1154450,1189150,1156870,1292570,1175265,1438983,1185376,1286744,1280565,
1340235,1328470,1483850,1358595,1486845,1392368,1464592,1466150,1747930,1468324,
1749212,1511930,1598470,1669910,2062570,1798875,1870245,2082464,2090656,2236570,
2429030,2652728,2941672,2723792,2874064,2728726,3077354,2739704,2928136,2802416,
2947216,2803580,3716164,3276856,3721544,3606850,3892670,3786904,4300136,3805264,
4006736,4238984,4314616,4246130,4488910,4259750,4445050,4482765,5120595,4532710,
6135962,4604776,5162744,5123090,5504110,5147032,5843048,5232010,5799542,5357625,
5684679,5385310,5812130,5459176,5495264,5726072,6369928,5730615,6088905,5864660,
7489324,6329416,6371384,6377175,6680025,6955216,7418864,6993610,7158710,7275532,
7471508,7288930,8221598,7489112,7674088,7577350,8493050,7677248,7684672,7800544,
7916696,7850512,8052488,8262136,8369864,8619765,9627915,9071685,9498555,9199496,
9592504,9339704,9892936,9363584,9437056};
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int t=0;
int i;
for(i=0;i<=105;i++)
{
if(dp[i][0]>=n&&dp[i][0]<=m&&dp[i][1]>=n&&dp[i][1]<=m)
t++;
}
printf("%d\n",t);
for(i=0;i<=105;i++)
{
if(dp[i][0]>=n&&dp[i][0]<=m&&dp[i][1]>=n&&dp[i][1]<=m)
printf("%d %d\n",dp[i][0],dp[i][1]);
}
}
return 0;
}
D題 Cayley公式
n^(n-2)
G非常可惡的動規，還以為要用什么數學方法，DP真是博大精深啊。。。多謝AngelClover的提示
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define INF 999999999
#define OFFSET 4000
int dp[41][8001];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i,j;
for(i=0;i<=n;i++)
for(j=0;j<=8000;j++)
dp[i][j]=INF;
dp[0][OFFSET]=0;
int t;
scanf("%d",&t);
dp[1][OFFSET+t]=0;
dp[1][OFFSET-t]=0;
for(i=1;i<=n-1;i++)
{
scanf("%d",&t);
for(j=OFFSET-100*i;j<=OFFSET+100*i;j++)
{
if(dp[i][j]!=INF)
{
dp[i+1][j+t]=min(dp[i+1][j+t],dp[i][j]+(j-OFFSET)*t);
dp[i+1][j-t]=min(dp[i+1][j-t],dp[i][j]-(j-OFFSET)*t);
}
}
//for(j=OFFSET-10;j<=OFFSET+10;j++)
//{
//
// printf("%d ",dp[i+1][j]);
// }
//printf("\n");
}
double res=INF;
for(i=0;i<=8000;i++)
{
if(dp[n][i]<res)
res=dp[n][i];
}
printf("%.2lf\n",res);
}
return 0;
}
I 離線算法 很強大啊，不過我在想 如果可以動態破壞的話，就只能用線段樹了么？
感謝cl大牛
#include<cstdio>
#include<iostream>
#include<algorithm>
/**//*
x是排好序的去掉的數
q[i].ID是詢問的原本位置
q[i].kth是詢問第kth個數
q按kth排序
ans就是答案
*/
#define MAX 50000
#define INF 0x7FFFFFFF
using namespace std;
struct Node
{
int ID;
int kth;
bool operator < (Node p)
{
return kth<p.kth;
}
};
int n;
int x[MAX];
int m;
Node q[MAX];
int ans[MAX];
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
x[++n]=INF;
sort(x+1,x+n+1);
int nn=1;
for(int i=2;i<=n;i++) if(x[i]!=x[nn]) x[++nn]=x[i];
n=nn;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&q[i].kth);
q[i].ID=i;
}
sort(q+1,q+m+1);
for(int i=1,j=1;i<=m;i++)//i代表第幾個詢問
{
while(x[j]-j<q[i].kth)
j++;
ans[q[i].ID]=(j-1)+q[i].kth;
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
putchar('\n');
}
return 0;
}
J題 動態規劃 n^3水掉。。。 應該是有更好的方法，還要繼續學習啊
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 999999999
int dp[1001][1001];
char str[2000];
int c[1001];
int cc(int i,int j)
{
int res=0;
if(str[i]!='(')
res+=c[i];
if(str[j]!=')')
res+=c[j];
return res;
}
int main()
{
while(scanf("%s",str+1)!=EOF)
{
int i,j;
int n=strlen(str+1);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
dp[i][j]=INF;
}
for(i=1;i<=n;i++)
scanf("%d",&c[i]);
if(n&1)
{
printf("-1\n");
continue;
}
for(i=1;i<=n-1;i++)
dp[i][i+1]=cc(i,i+1);
for(i=3;i<=n-1;i+=2)//i為區間長度
{
for(j=1;j<=n-i;j++)
{
int k;
int temp=INF;
for(k=2;k<i;k+=2)
{
if(dp[j][j+k-1]+dp[j+k][j+i]<temp)
temp=dp[j][j+k-1]+dp[j+k][j+i];
}
dp[j][j+i]=min(temp,dp[j+1][j+i-1]+cc(j,j+i));
}
}
printf("%d\n",dp[1][n]);
}
return 0;
}
關于本題的另一個解法：
初始state=0
遇到'(' state++;
遇到')' state--
如果當前state<0說明')'比這個'('多
然后就要把')'變成'('
這部貪心把花費最小的')'變成'('
這樣一遍后'('的個數會>=')'
然后反向過來反過來弄一遍
這樣'('就==')'了
就得到解了
比如
( ( ) ) ) (
123456
下面的是花費
那么到
( ( ) ) )
這個狀態的時候是不是就<0了
就是不合法了
就變成
( ( ( ) )了
這樣就>0了，而且花費最少
然后最終變成
( ( ( ) ) (
然后反過來
(
的時候就不合法了
改成
)
然后就變成
((()))
就是答案了