秋实大哥与线段树
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
“学习本无底，前进莫徬徨。” 秋实大哥对一旁玩手机的学弟说道。
秋实大哥是一个爱学习的人，今天他刚刚学习了线段树这个数据结构。
为了检验自己的掌握程度，秋实大哥给自己出了一个题，同时邀请大家一起来作。
秋实大哥的题目要求你维护一个序列，支持两种操作：一种是修改某一个元素的值；一种是询问一段区间的和。
Input
第一行包含一个整数n，表示序列的长度。
接下来一行包含n个整数ai，表示序列初始的元素。
接下来一行包含一个整数m，表示操作数。
接下来m行，每行是以下两种操作之一：
1 x v : 表示将第x个元素的值改为v
2 l r : 表示询问[l,r]这个区间的元素和
1≤n，m，v，ai≤1000001≤n，m，v，ai≤100000，1≤l≤r≤n1≤l≤r≤n。
Output
对于每一个22 ll rr操作，输出一个整数占一行，表示对应的答案。
Sample input and output
| Sample Input | Sample Output |
|---|---|
3 |
3 |
Source
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; int m,n;
int a[]; struct data
{
long long sum;
}node[]; void build(int pos,int l,int r)
{
if(l==r)
{
node[pos].sum=a[l];
return ;
}
int mid=l+r>>;
int lson=pos*,rson=lson+;
build(lson,l,mid);
build(rson,mid+,r);
node[pos].sum=node[lson].sum+node[rson].sum;
}
long long int query(int pos,int l,int r,int ql,int qr)
{
if(l==ql&&r==qr)return node[pos].sum;
int mid=l+r>>;
int lson=pos*,rson=lson+;
if(qr<=mid)return query(lson,l,mid,ql,qr);
else if(ql>mid)return query(rson,mid+,r,ql,qr);
else return query(lson,l,mid,ql,mid)+query(rson,mid+,r,mid+,qr);
}
void modify(int pos,int l,int r,int m,int v)
{
if(l==r)
{
node[pos].sum=v;
return ;
}
int mid=l+r>>;
int lson=pos*,rson=lson+;
if(m<=mid)modify(lson,l,mid,m,v);
else modify(rson,mid+,r,m,v);
node[pos].sum=node[lson].sum+node[rson].sum;
}
int main()
{
int caozuo,x,v;
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&a[i]);
build(,,n);
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&caozuo,&x,&v);
if(caozuo==)
{
modify(,,n,x,v);
}
else
{
printf("%lld",query(,,n,x,v));
puts("");
}
}
return ;
}
QAQ
描述
一元 n 次多项式可用如下的表达式表示：
其中，aixi 称为i次项，ai称为i次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：
1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。
2. 多项式中只包含系数不为0 的项。
3. 如果多项式n 次项系数为正，则多项式开头不出现“+”号，如果多项式n 次项系数为负，则多项式以“-”号开头。
4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0 次的项，其系数的绝对值为1，则无需输出1）。如果x 的指数大于1，则接下来紧跟的指数部分的形式为“x^b”，其中b 为x 的指数；如果x 的指数为1，则接下来紧跟的指数部分形式为“x”； 如果x 的指数为0，则仅需输出系数即可。
5. 多项式中，多项式的开头、结尾不含多余的空格。
格式
输入格式
共有2 行。
第一行 1 个整数，n，表示一元多项式的次数(1 ≤ n ≤ 100)。
第二行有 n+1 个整数，其中第i 个整数表示第n-i+1 次项的系数，每两个整数之间用空格隔开。
多项式各次项系数的绝对值均不超过100。
输出格式
共1 行，按题目所述格式输出多项式。
样例1
样例输入1
5
100 -1 1 -3 0 10
样例输出1
100x^5-x^4+x^3-3x^2+10
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std; int n,a[];
int main()
{
scanf("%d",&n);
for(int i=n;i>=;--i)scanf("%d",&a[i]);
for(int i=n;i>=;--i)
{
if(a[i]==)
{
if(i==n)printf("x^%d",i);
else printf("+x^%d",i);
}
if(a[i]==-)printf("-x^%d",i);
if(a[i]<-)printf("%dx^%d",a[i],i);
if(a[i]>)
{
if(i==n)printf("%dx^%d",a[i],i);
else printf("+%dx^%d",a[i],i);
}
}
if(a[]==)printf("+x");
if(a[]<)printf("%dx",a[]);
if(a[]>)printf("+%dx",a[]); if(a[]>)printf("+%d",a[]);
if(a[]<)printf("%d",a[]);
puts("");
return ;
}
QAQ心疼蠢哭的自己
纯模拟QAQ
注意最后一项和倒二项还有第一项的判断 其他都很简单
最后一项直接输出 不带x的
倒二项没有^1
第一项如果是正的不能直接输出‘+’
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000005
using namespace std;
int n;
int a[];
int main()
{
cin>>n;
int time=n+;
for(int i=n;i>=;--i)
{
scanf("%d",&a[i]);
}
for(int i=n;i>=;--i)
{
if(i==n)
{
if(a[i]==)printf("x^%d",i);
if(a[i]==-)printf("-x^%d",i);
if(a[i]!=&&a[i]!=&&a[i]!=-) printf("%dx^%d",a[i],i);
}
else if(i>&&i<n)
{
if(a[i]==)printf("+x^%d",i);
else if(a[i]==-)printf("-x^%d",i);
else if(a[i]>) printf("+%dx^%d",a[i],i);
else if(a[i]<)printf("%dx^%d",a[i],i);
else continue;
}
else
{
if(a[i]==)printf("+x",i);
else if(a[i]==-)printf("-x",i);
else if(a[i]>) printf("+%dx",a[i]);
else if(a[i]<)printf("%dx",a[i]);
else continue;
}
}
if(a[]>)printf("+%d",a[]);
if(a[]<)printf("%d",a[]);
return ;
}
背景
佳佳的魔法照片(Magic Photo)：如果你看过《哈利·波特》，你就会知道魔法世界里的照片是很神奇的。也许是因为小魔法师佳佳长的太帅，很多人都找他要那种神奇的魔法照片，而且还都要佳佳和他的MM的合照。那些照片可是非常珍贵的，他到底应该把照片给谁呢？
描述
一共有n个人（以1--n编号）向佳佳要照片，而佳佳只能把照片给其中的k个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值W[i]。然后将初始权值从大到小进行排序，每人就有了一个序号D[i]（取值同样是1--n）。按照这个序号对10取模的值将这些人分为10类。也就是说定义每个人的类别序号C[i]的值为(D[i]-1) mod 10 +1，显然类别序号的取值为1--10。第i类的人将会额外得到E[i]的权值。你需要做的就是求出加上额外权值以后，最终的权值最大的k个人，并输出他们的编号。在排序中，如果两人的W[i]相同，编号小的优先。
格式
输入格式
第一行输出用空格隔开的两个整数，分别是n和k。
第二行给出了10个正整数，分别是E[1]到E[10]。
第三行给出了n个正整数，第i个数表示编号为i的人的权值W[i]。
输出格式
只需输出一行用空格隔开的k个整数，分别表示最终的W[i]从高到低的人的编号。
样例1
样例输入1
10 10
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
样例输出1
10 9 8 7 6 5 4 3 2 1
限制
1秒
提示
对于50%的数据，n<=200；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 50005
using namespace std; struct data
{
int w,id;
}node[maxn];
bool cmp(data a,data b)
{
if(a.w==b.w)return a.id<b.id;
else return a.w>b.w;
}
int n,k;
int e[];
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=;++i)scanf("%d",&e[i]);
for(int i=;i<=n;++i)
{
scanf("%d",&node[i].w);
node[i].id=i;
}
sort(node+,node++n,cmp);
for(int i=;i<=n;++i)
{
node[i].w+=e[(i-)%+];
}
sort(node+,node++n,cmp);
for(int i=;i<=k;i++)printf("%d ",node[i].id);
puts("");
return ;
}
++rp
1020 孪生蜘蛛
在G城保卫战中，超级孪生蜘蛛Phantom001和Phantom002作为第三层防卫被派往守护内城南端一带极为隐秘的通道。
根据防护中心的消息，敌方已经有一只特种飞蛾避过第二层防卫，直逼内城南端通道入口。但优秀的蜘蛛已经在每个通道内埋下了坚固的大网，无论飞蛾进入哪个通道，他只有死路一条！（因为他是无法挣脱超级蛛网的）
现在，001和002分别驻扎在某两个通道内。各通道通过内线相通，通过每条内线需要一定的时间。当特种飞蛾被困某处，001或002会迅速赶来把它结果掉（当然是耗时最少的那个）。
001跟002都想尽早的完成任务，他们希望选择在最坏情况下能尽早完成任务的方案。
第一行为一个整数N (N<=100) 表示通道数目。
接下来若干行每行三个正整数a,b,t 表示通道a,b有内线相连，通过的时间为t。(t<=100)
（输入保证每个通道都直接/间接连通）
两个不同的整数x1,x2，分别为001，002驻扎的地点。（如果有多解，请输出x1最小的方案，x1相同则输出x2最小的方案）
3
1 2 5
2 3 10
3 1 3
1 2