Q1028 - Unit7 - 堆积木From Admin Normal (OI) |
||||||||
|---|---|---|---|---|---|---|---|---|
对于最优方案： 因为F(N)-（w1+w2+..wn-1)<F(1)-(w2+...+wn-1+wn) 化简得 F(n)+wn<F1+w1 调整ing。。。 也就是说对于最优方案有 Fi+wi<Fi-1+wi-1
Program block;
uses math;
const
maxn=50000;
var
n,i,j,ans,totw:longint;
w,f:array[1..maxn] of longint;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=w[(i+j) div 2]+f[(i+j) div 2];
repeat
while (w[i]+f[i]<m) do inc(i);
while (w[j]+f[j]>m) do dec(j);
if i<=j then
begin
p:=w[i];w[i]:=w[j];w[j]:=p;
p:=f[i];f[i]:=f[j];f[j]:=p;
inc(i);dec(j);
end;
until i>j;
if (l<j) then qsort(l,j);
if (i<r) then qsort(i,r);
end;
begin
read(n);
for i:=1 to n do
begin
read(w[i],f[i]);
end;
qsort(1,n);
ans:=-f[1];
totw:=0;
for i:=1 to n do
begin
ans:=max(ans,totw-f[i]);
inc(totw,w[i]);
end;
writeln(ans);
end.
|
||||||||
Category Archives: DefaultCategory
Tyvj Q1033(线性扫描）
Q1033 - Unit9 - 智力值From Admin Normal (OI) |
||||||
|---|---|---|---|---|---|---|
|
||||||
每次贪心贪比他聪明的人中最不聪明的
const
maxn=5000;
var
n,i,j,now,tot:longint;
a:array[1..maxn] of longint;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=a[(l+r) div 2];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if (l<j) then qsort(l,j);
if (i<r) then qsort(i,r);
end;
begin
read(n,now);
tot:=0;
for i:=1 to n do read(a[i]);
qsort(1,n);
for i:=1 to n do
begin
if (now<a[i]) then inc(now,2)
else inc(tot);
end;
writeln(tot+now);
end.
Tyvj P2064(点的向上维护）
P2064 - 「Poetize10」能量获取From lydliyudong Normal (OI) |
||||||
|---|---|---|---|---|---|---|
|
||||||
此题贪心 贪最小的点，易证必最优解
Program energy;
const
maxn=1000;
var
n,i,j,ans:longint;
f,e,w,num,hpos:array[0..maxn] of longint;
procedure swap(var a,b:longint);
var
t:longint;
begin
t:=a;a:=b;b:=t;
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=e[(l+r) div 2];
repeat
while (e[i]<m) do inc(i);
while (e[j]>m) do dec(j);
if (i<=j) then
begin
swap(e[i],e[j]);
swap(f[i],f[j]);
swap(w[i],w[j]);
swap(num[i],num[j]);
inc(i);dec(j);
end;
until i>j;
if (l<j) then qsort(l,j);
if (i<r) then qsort(i,r);
end;
procedure pour(x:longint);
var
noww,i,j:longint;
begin
noww:=maxlongint;
i:=x;
while (i<>0) do
begin
noww:=min(noww,w[i]);
i:=hpos[f[i]];
end;
if (noww<e[x]) then exit;
inc(ans);
i:=x;
while (i<>0) do
begin
dec(w[i],e[x]);
i:=hpos[f[i]];
end;
end;
begin
readln(n);
for i:=1 to n do
begin
read(f[i],e[i],w[i]);
num[i]:=i;
end;
qsort(1,n);
hpos[0]:=0;
for i:=1 to n do hpos[num[i]]:=i;
// for i:=1 to n do write(f[i],' ',e[i],' ',w[i]);
ans:=0;
for i:=1 to n do pour(i);
writeln(ans);
end.
幸运字符串(ansistring)
幸运字符串(string)
【问题描述】
对于一个只包含0和1的字符串，如果A是幸运的，B也是幸运的，那么1AB1也是一个幸运的串。现在定义”0”是一个幸运字符串，请判断给定的字符串S是否是幸运的。
【输入格式】
第一行一个数字T，表示数据组数。
接下来T组数据，第一行字符串长度n，接下来一行一个只含01的字符串。
【输出格式】
T行，第i个串如果是幸运字符串那么输出”YES”，否则输出”NO”。
【样例输入】
3
4
1001
7
1100101
7
0110011
【样例输出】
YES
YES
NO
【数据范围】
30%的数据满足n<=100；
50%的数据满足n<=300；
100%的数据满足n<=800，T<=10
未1A的原因，又没改ansistring
//string
var
n,tt,i,j,now:longint;
s:ansistring;
function sort(i,j:longint):boolean;
var
k:longint;
begin
if (i=j) then
begin
if s[i]='0' then exit(true)
else exit(false);
end;
{
if (s[i]='1') and (s[j]='1') then
begin
for k:=i+1 to j-2 do
if (sort(i+1,k)) and (sort(k+1,j-1)) then exit(true);
end;
}
exit(false);
end;
begin
assign(input,'string.in');
assign(output,'string.out');
reset(input);
rewrite(output);
readln(tt);
while (tt>0) do
begin
readln(n);
readln(s);
while (true) do
begin
i:=pos('1001',s);
if (i=0) then break;
delete(s,i,2);
delete(s,i+1,1);
dec(n,3);
end;
if (sort(1,n)) then writeln('YES')
else writeln('NO');
dec(tt);
end;
close(input);
close(output);
end.
传纸条(看清题目）
传纸条(message)
【题目描述】
小N和小A上课喜欢传纸条。
传纸条是有风险的，为了在老师发现的时候不知道他们在讨论什么内容，他们发明了一系列的加密方式。
其中有一种是这样的：一个数字由两个字符串a和b表达，这个数字就是b在a中匹配的位置。比如，a=”abcd”，b=”c”，那么这个数字就是3。
但是这样会出现一个问题，a和b能够表达两个不同的数字：比如，a=“ababa”，b=”aba”时，那个数字可以是1也可以是3。
他们对这种现象很好奇，现在给定一个字符串a，求一个整数x使得对于任意一个长度大于x的串b，这一问题都不会出现。
【输入数据】
一个仅由小写字母组成的字符串a
【输出数据】
一行一个整数，表示x的最小值
【样例输入】
ababa
【样例输出】
3
【数据范围】
对于50%的数据，a的长度≤10,
对于100%的数据，a的长度≤100.
Program message;
var
n,i,j,k,l,ans:longint;
s:string;
function min(a,b:longint):longint;
begin
if (a<b) then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
if (a>b) then exit(a) else exit(b);
end;
begin
assign(input,'message.in');
assign(output,'message.out');
reset(input);
rewrite(output);
readln(s);
n:=length(s);
ans:=0;
for i:=1 to n do
for j:=i+1 to n do
begin
k:=i;
l:=j;
while ((s[k]=s[l]) and (l<=n)) do
begin
inc(k);
inc(l);
if (l>n) then break;
end;
ans:=max(ans,k-i);
end;
writeln(ans);
close(input);
close(output);
end.
HDU 1865(高精斐波那契）
高精斐波那契
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<string>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (200+10)
#define F (1000)
struct bign
{
int len;
int a[1000];
bign operator+(const bign& b)
{
bign c;
memset(c.a,0,sizeof(c.a));
c.len=max(len,b.len)+1;
for (int i=1;i<=c.len;i++)
{
c.a[i]+=a[i]+b.a[i];
c.a[i+1]+=c.a[i]/F;
c.a[i]=c.a[i]%F;
}
if (c.a[c.len]==0&&c.len>1) c.len--;
return c;
}
bign operator= (int num)
{
memset(a,0,sizeof(a));
a[1]=num;
len=1;
return *this;
}
};
bign f[MAXN];
int n;
int main()
{
cin>>n;
f[1]=1;f[2]=2;
for (int i=3;i<=200;i++)
f[i]=f[i-1]+f[i-2];
for (int i=1;i<=n;i++)
{
string s;
cin>>s;
int j=s.length();
cout<<f[j].a[f[j].len];
for (int k=f[j].len-1;k>=1;k--)
{
if (f[j].a[k]<100) cout<<"0";
if (f[j].a[k]<10) cout<<"0";
printf("%d",f[j].a[k]);
}
cout<<"n";
}
// for (int i=1;i<=200;i++) cout<<f[i].len;
/*
for (int j=1;j<=200;j++)
{
cout<<f[j].a[f[j].len];
for (int k=f[j].len-1;k>=1;k--)
{
if (f[j].a[k]<100) cout<<"0";
if (f[j].a[k]<10) cout<<"0";
printf("%d",f[j].a[k]);
}
cout<<"n";
}*/
return 0;
}
行车(a1*b1+a1*b2+..a1*bn+a2*b1+…an*bn=(a1+..an)(b1+..bn) )
行车
(bicycle.pas/cpp)
题目描述
骑在自行车上，让微风追逐着他衣角，在不经意间捕获着一颗颗芳心，骄阳似乎也没有此时的他耀眼，这便是机房的骄傲——建德！
这是每天都会发生在附中门口的一幕。而为了每天能够领略不同的风景，捕获更多的芳心，建德打算制定n 条线路。为了简化起见，我们把这个世界想象成一个平面直角坐标系，而建德所在的福建师大附中则为原点。由于建德不能绕的太进，他每次路线的目的地都被限制在一个对应的右上角为(x, y)，左下角为(-x,-y)的矩形内。
每次建德都会从原点直接沿直线走到目的地。显然，他走过了一个向量，这被数学控的“毛毡”称为这次的路线向量。他为了更好地规划线路，为每条线路定义了一个无聊值，即这次的路线向量和其余所有乊前的线路的向量的点积和【对于向量(x1,y1),(x2,y2),他们的点积和即为x1*x2+y1*y2】。建德希望合理的选择目的地，使得所有线路的无聊值乊和最小。
输入格式
第一行一个正整数n ，表示建德打算制定n 条旅行线路。
接下来 n 行，每行两个整数x , y ，描述一个限制目的地的矩形。
输出格式
一行一个整数，即最小的无聊值，保留 2 位小数。
样例输入
2
1 2
2 1
样例输出
-4.00
数据范围与约定
对于10% 的数据，保证0<n<=5，0<x,y<=5。
对于 30% 的数据，保证0<n<=20，0<x,y<=100。
对于 100% 的数据，保证0<n<=200，0<x,y<=200。
首先 根据公式 n个数和m个数两两相乘的结果为n个数的和与m个数的和的积
而且x和y互不影响
于是套公式-两两相乘/2-交集 结果为 f(n)= （x1+..+xn)^2+x1^2+..xn^2 )/2
易证 f(n)=(x1+...+xn-1)* xn + f(n-1)
所以 xn 要么最大，要么最小 才能使 f(n)有最大/最小值
因为不知道 (x1+..x(n-1)的正负 所以只能靠猜（ 既考虑最大，也考虑最小）
回到原公式 显然 要是 f(n)有最小值 就要另 （x1+..+xn)有最小值
于是就是分组背包各种做……
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (200+10)
#define MAXV ((40000+100)*2)
#define MAXX (200+10)
#define f(i,j) f[ (i) ][ (j)+20000 ]
int n;
long long ans=0;
bool f[MAXN][MAXV];
int x[MAXN];
int y[MAXN];
int sqr(int x)
{
return x*x;
}
int main()
{
freopen("bicycle.in","r",stdin);
freopen("bicycle.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
ans-=(long long)(sqr(x[i]))+sqr(y[i]);
}
memset(f,0,sizeof(f));
f(0,0)=1;
for (int i=1;i<=n;i++)
for (int j=-i*200;j<=i*200;j++)
f(i,j)=f(i-1,j-x[i])||f(i-1,j+x[i]);
int j=0;
while (!f(n,j)&&!f(n,-j)) j++;
ans+=(long long)j*j;
// cout<<j<<endl;
/* int j=0;
for (int i=0;i<=n;i++)
{
for (int j=-10;j<=10;j++)
cout<<f(i,j);
cout<<endl;
}
*/
memset(f,0,sizeof(f));
f(0,0)=1;
for (int i=1;i<=n;i++)
for (int j=-i*200;j<=i*200;j++)
f(i,j)=f(i-1,j-y[i])||f(i-1,j+y[i]);
j=0;
while (!f(n,j)&&!f(n,-j)) j++;
ans+=(long long)j*j;
cout.setf(ios::fixed);
cout.precision(2);
cout<<double(ans)/2<<endl;
// while (1);
return 0;
}
Tyvj Q1024(double的使用）
在C++中 double会以牺牲最小数为代价换取高位
另外请看好题目是求整数部分还是四舍五入
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<string>
using namespace std;
#define MAXN (1000+10)
int a[MAXN][MAXN],n;
int main()
{
long double ans=0.0;
scanf("%d",&n);
long long all=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
all+=((long long)n-i+1)*((long long)n-j+1);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
ans+=(long double)(a[i][j])*(long double)(n-i+1)*(long double)(n-j+1)*(long double)(i*j);
// cout<<ans<<' ';
}
cout.setf(ios::fixed);
cout.precision(0);
cout<<trunc(ans/(long double)(all))<<endl;
return 0;
}
Tyvj P2060(别把字符搞萎）
这题送分题居然wa了
我仔仔细细地看了看题目……发现不慎把Yes 和No打萎了……
仅以为戒
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<string>
using namespace std;
#define MAXN (10000+10)
int w[MAXN];
int a[MAXN];
string s;
long long n,t;
int main()
{
// freopen("read.in","r",stdin);
// freopen("read.out","w",stdout);
cin>>t>>n;
for (int i=(int)('a');i<=(int)('z');i++) {
cin>>w[i];
}
// cout<<w[112];
for (int i=1;i<=n;i++)
{
cin>>s;
a[i]=0;
for (int j=0;j<s.length();j++)
{
s[j]=tolower(s[j]);
// cout<<w[(tolower(s[i]))]<<' ';
a[i] =a[i]+ w[s[j]];
// cout<<a[i]<<' '<<endl;
}
}
sort(a+1,a+1+n);
// for (int i=1;i<=n;i++) cout<<a[i]<<' ';
for (int i=1;i<=n;i++)
{
t-=(long long)(a[i]);
if (t<(long long)0)
{
cout<<"Non";
cout<<(i-1)<<endl;
return 0;
}
}
cout<<"Yesn"<<t<<endl;
return 0;
}
数字 （求2类数∩的方法）
数字
(num.c/cpp/pas)
【问题描述】
一个数字被称为好数字当他满足下列条件：
1. 它有2*n个数位，n是正整数(允许有前导0)。
2. 构成它的每个数字都在给定的数字集合S中。
3. 它前n位之和与后n位之和相等或者它奇数位之和与偶数位之和相等
例如对于n=2,S={1,2}，合法的好数字有1111,1122,1212,1221,2112,2121,2211,2222这样8种。
已知n，求合法的好数字的个数mod 999983。
【输入格式】
第一行一个数n。
接下来一个长度不超过10的字符串，表示给定的数字集合。
【输出格式】
一行一个数字表示合法的好数字的个数mod 999983。
【样例输入】
2
0987654321
【样例输出】
1240
【数据规模】
对于20%的数据，n≤7。
对于100%的.据,n≤1000,|S|≤10。
这题难点在求前n位之和与后n位之和相等与它奇数位之和与偶数位之和相等的交集
……
记得第一个数一定要（long long ) c++中对 3000这样的常量都是算int的，而等号优先级最低
另外本题是乘法原理+加法原理
先用乘法原理 求出 A=x a=y B=y b=x 的方案数 记得%F
然后将所有的情况相加++
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
#include<iostream>
using namespace std;
#define F (999983)
#define MAXN (1000+10)
#define MAXM (10000+10)
int n,m;
char s[100];
int a[100],siz=0;
int f[MAXN][MAXM];
int main()
{
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
scanf("%d",&n);
scanf("%s",s);
memset(f,0,sizeof(f));
for (int i=0;i<strlen(s);i++)
a[++siz]=s[i]-'0';
// for (int i=1;i<=siz;i++) cout<<a[i]<<' ';
sort(a+1,a+1+siz);
for (int i=1;i<=siz;i++)
{
f[1][a[i]]=1;
// cout<<a[i]<<' ';
}
f[0][0]=1;
for (int i=2;i<=n;i++)
for (int j=i*a[1];j<=i*a[siz];j++)
{
/* if (j==18)
{
cout<<'s';
}
*/ for (int k=1;k<=siz;k++)
if (j-a[k]>=0)
f[i][j]=(f[i][j]+(f[i-1][j-a[k]])%F)%F;
}
long long ans=0;
for (int j=0;j<=n*a[siz];j++)
{
// if (f[n][j]>0) cout<<j<<' '<<f[n][j]<<endl;
ans=ans+(long long)(f[n][j])*(long long)(f[n][j]);
ans%=F;
}
// cout<<(2*ans)%F<<endl;
/*现在开始几算相同的情况
A 前奇 B 前偶 a 后奇 b 后偶
显然 A+a=B+b A+a=B+b ->A=b&&sa=B
则答案为
∑（a*A*b*B) 这4个数为(此处a,A,b,B指当它们正好等于这个值的方案数
∑ （a^2*A^2)
∑ (f[n/2.i]^2*f[n/2+n%2,i])
*/
// cout<<ans<<endl;
long long tmpA=0;
for (int i=(n/2)*a[1];i<=(n/2)*a[siz];i++)
tmpA=(tmpA+(long long)f[n/2][i]*f[n/2][i])%F;
long long tmpB=0;
for (int i=(n/2+n%2)*a[1];i<=(n/2+n%2)*a[siz];i++)
tmpB=(tmpB+(long long)f[n/2+n%2][i]*f[n/2+n%2][i])%F;
// cout<<tmpA<<' '<<tmpB;
// cout<<tmpA*tmpB<<endl;
ans=(ans*2)%F;
// cout<<ans<<endl;
{
// cout<<ans<<' '<<tmpA*tmpB;
}
ans=(ans-tmpA*tmpB+F*((tmpA*tmpB)/F)+F)%F;
cout<<ans<<endl;
// while(1);
return 0;
}