水题
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 100005
#define eps 1e-8
#define INF 0x7FFFFFFF
typedef long long ll;
char s[1005];
int main(){
int n,m,t,i;
cin>>t;
while(t--){
cin>>n>>m;
if(n>m){
int tt = n;
n = m;
m = tt;
}
cin>>s;
int k = 0;
int l = strlen(s);
for(i=0;i<n;i++){
for(int j =0;j<m;j++){
cout<<s[k++];
}
cout<<endl;
}
}
return 0;
}
题意：把一个n进制数转换为[(1+√5)/2]进制
根据题目给的两个公式，011->100，0200->1001可以推广到 [0][n][0][0]->[n/2][n%2][0][n/2]，由于[(1+√5)/2]^50 > 10^10，所以数组开100个就够了，小数点前小数点后各50个数字。开始时把n放在数组第50位，则最多进行50次循环的变换就能变为0、1组成的形式。
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 100005
#define eps 1e-7
#define INF 0x7FFFFFFF
#define ff sqrt(5.0)
typedef long long ll;
int a[110];
int main(){
int n,i,flag;
while(scanf("%d",&n)!=EOF){
if(n==1){
cout<<1<<endl;
continue;
}
memset(a,0,sizeof(a));
a[50] = n;
flag = 1;
while(flag){
flag = 0;
for(i=105;i>=1;i--){
if(a[i]>1){
flag = 1;
a[i-1] += a[i]/2;
a[i+2] += a[i]/2;
a[i] %= 2;
}
}
for(i=105;i>=2;i--){
if(a[i]&&a[i-1]){
flag = 1;
int temp = min(a[i],a[i-1]);
a[i-2] += temp;
a[i] -= temp;
a[i-1] -= temp;
}
}
}
int ll, rr;
for(i=0;i<110;i++){
if(a[i]){
ll = i;
break;
}
}
for(i=105;i>0;i--){
if(a[i]){
rr = i;
break;
}
}
for(i=ll;i<=rr;i++){
cout<<a[i];
if(i==50) cout<<".";
}
cout<<endl;
}
return 0;
}
有n个问题各有不同的分值，两个人回答问题，假设B答对每道题的概率为0.5，问A至少得多少分才能使不输给B的概率不小于P。
这个思路是别人博客中摘的：我们要算A不输给B的概率。如果我们知道A得每种得分的频数y。和A不小于B得分的频数x.那么p=x/y。先只需x/y>=p。x>=y*p。就行了。因为答每到题有两种可能。所以B得分就有y=2^n种可能。现在关键就是求x了。要使得分最小。我们可以先用背包求出B得每种得分的方案数。让后得分从小到大累加方案数。第一个使得x>=y*p的得分就是最小得分。
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 100005
#define eps 1e-7
#define INF 0x7FFFFFFF
#define ff sqrt(5.0)
typedef long long ll;
int dp[40010],score[50];
int main(){
int n,t,i;
ll m;
double p;
ll cnt,sum;
scanf("%d",&t);
while(t--){
memset(dp,0,sizeof(dp));
sum = cnt = 0;
scanf("%d%lf",&n,&p);
m = 1LL<<n;
dp[0] = 1;
for(i=0;i<n;i++){
scanf("%d",&score[i]);
sum += score[i];
}
for(i=0;i<n;i++){
for(int j=sum;j>=score[i];j--){
if(dp[j-score[i]]) dp[j] += dp[j-score[i]];
}
}
ll x = ceil(p*m);
for(i=0;i<=sum;i++){
cnt += dp[i];
if(cnt>=x){
cout<<i<<endl;
break;
}
}
}
return 0;
}
二维线段树。做的时候虽然感觉像一个二维的线段树不过还是勇敢的T了一发。二维线段树不会，网上没找到讲解，找了个代码先当模板用。一直在想二维的树是怎么建的，看了代码感觉行被当做一个索引，在每个列上建一个树，每一个树上还是父节点保存着子节点的最大最小值，查询的时候像和一维的思路类似，只不过要先从行序列开始找。
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 810
#define eps 1e-7
#define INF 0x7FFFFFFF
#define ff sqrt(5.0)
typedef long long ll;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int ds[MAXN<<2][MAXN<<2];
int db[MAXN<<2][MAXN<<2];
int n;
int A[MAXN][MAXN];
struct node
{
int minm,maxm;
};
void pushup(int k,int rt)
{
db[k][rt]=max(db[k][rt<<1],db[k][rt<<1|1]);
ds[k][rt]=min(ds[k][rt<<1],ds[k][rt<<1|1]);
for (int i=(k>>1);i;i>>=1){
db[i][rt]=max(db[i<<1][rt],db[i<<1|1][rt]);
ds[i][rt]=min(ds[i<<1][rt],ds[i<<1|1][rt]);
}
}
void buildc(int k,int l,int r,int rt)
{
db[k][rt]=-INF;
ds[k][rt]=INF;
if (l>=r){
return;
}
int m=(l+r)>>1;
buildc(k,lson);
buildc(k,rson);
}
void buildr(int l,int r,int rt)
{
buildc(rt,1,n,1);
if (l>=r){
return;
}
int m=(l+r)>>1;
buildr(lson);
buildr(rson);
}
node queryc(int k,int c1,int c2,int l,int r,int rt)
{
if (c1<=l && r<=c2){
node x;
x.maxm=db[k][rt];
x.minm=ds[k][rt];
return x;
}
int m=(l+r)>>1;
if (m<c1){
return queryc(k,c1,c2,rson);
}
else
if (m>=c2){
return queryc(k,c1,c2,lson);
}
else{
node a=queryc(k,c1,c2,lson);
node b=queryc(k,c1,c2,rson);
node c;
c.minm=min(a.minm,b.minm);
c.maxm=max(a.maxm,b.maxm);
return c;
}
}
node queryr(int r1,int r2,int c1,int c2,int l,int r,int rt)
{
if (r1<=l && r<=r2)
{
return queryc(rt,c1,c2,1,n,1);
}
int m=(l+r)>>1;
if (r2<=m){
return queryr(r1,r2,c1,c2,lson);
}
else
if (r1>m){
return queryr(r1,r2,c1,c2,rson);
}
else{
node a=queryr(r1,r2,c1,c2,lson);
node b=queryr(r1,r2,c1,c2,rson);
node c;
c.maxm=max(a.maxm,b.maxm);
c.minm=min(a.minm,b.minm);
return c;
}
}
void updatec(int val,int k,int C,int l,int r,int rt)
{
if (l>=r)
{
db[k][rt]=val;
ds[k][rt]=val;
for (int i=(k>>1);i;i>>=1){
db[i][rt]=max(db[i<<1][rt],db[i<<1|1][rt]);
ds[i][rt]=min(ds[i<<1][rt],ds[i<<1|1][rt]);
}
return;
}
int m=(l+r)>>1;
if (C<=m) updatec(val,k,C,lson);
else updatec(val,k,C,rson);
pushup(k,rt);
}
void updater(int val,int R,int C,int l,int r,int rt)
{
if (l>=r)
{
updatec(val,rt,C,1,n,1);
return;
}
int m=(l+r)>>1;
if (R<=m) updater(val,R,C,lson);
else updater(val,R,C,rson);
}
int main()
{
int t,k = 1,m,ll,rr,ss,i;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
buildr(1,n,1);
for (i=1;i<=n;i++){
for (int j=1;j<=n;j++){
scanf("%d",&A[i][j]);
updater(A[i][j],i,j,1,n,1);
}
}
scanf("%d",&m);
printf("Case #%d:\n",k++);
int r1,r2,c1,c2;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&ll,&rr,&ss);
r1=max(ll-ss/2,1);
r2=min(ll+ss/2,n);
c1=max(rr-ss/2,1);
c2=min(rr+ss/2,n);
node ans=queryr(r1,r2,c1,c2,1,n,1);
int ret=(ans.maxm+ans.minm)/2;
printf("%d\n",ret);
updater(ret,ll,rr,1,n,1);
}
}
return 0;
}