1285开始用STL编程
1286 约瑟夫环
1098 归并排序
1261 C语言8.27
1023 坑爹的黑店（水题）
1059 1065 图砖
1068 计算并集
移动的盒子（Boxes in a Line,UVa 12657）
#include<iostream>
#include<algorithm>
using namespace std;
int shu[100010]={0};
int main(){
int nn,mm,ti=0;
for(int i=0;i<100010;i++)
shu[i]=i+1;
while(cin>>nn>>mm){
ti++;
int re=0;
while(mm--){
int a,b,c,x,y,t;
cin>>a;if(a!=4)cin>>b>>c;
for(int l=0;l<nn;l++){
if(shu[l]==b)x=l;
if(shu[l]==c)y=l;
}
if(a==1){
t=shu[x];
if(x<y){
for(int m=x;m<y-1;m++)
shu[m]=shu[m+1];
shu[y-1]=t;
}
else{
for(int n=x;n>y;n--)
shu[n]=shu[n-1];
shu[y]=t;
}
}
else if(a==2){
t=shu[x];
if(x<y){
for(int m=x;m<y;m++)
shu[m]=shu[m+1];
shu[y]=t;
}
else{
for(int n=x;n>y+1;n--)
shu[n]=shu[n-1];
shu[y+1]=t;
}
}
else if(a==3){
t=shu[x];shu[x]=shu[y];shu[y]=t;
}
else if(a==4){
reverse(shu,shu+nn);
re++;
}
}
long long sum=0;
// for(int k=0;k<nn;k++)
// sum+=shu[k++];
if(nn%2==1){
long long ss=nn/2+1;
sum=ss*ss;
}
else if(re%2==0){
long long tt=nn/2;
sum=tt*tt;
}
else if(re%2==1){
long long rr=nn/2;
sum=rr*(rr+1);
}
cout<<"Case "<<ti<<": "<<sum<<endl;
}
return 0;
}
假定相同值的元素可能有多个
lower_bound 返回第一个符合条件的元素位置
upper_bound 返回最后一个符合条件的元素位置
equal_range 返回所有等于指定值的头/尾元素的位置，其实就是lower_bound和upper_bound
binary_search 返回是否有需要查找的元素。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<list>
using namespace std;
list<int>shu;
list<int>::iterator it1,it2;
int main(){
int n,m,ti=0;
while(scanf("%d %d",&n,&m)!=EOF){
ti++;
int re=0;
while(m--){
int a,b,c;
for(int i=1;i<=n;i++)
shu.push_back(i);
cin>>a;if(a!=4)cin>>b>>c;
it1=lower_bound(shu.begin(),shu.end(),b);
it2=lower_bound(shu.begin(),shu.end(),c);
if(a==1){
shu.insert(it2,b);
shu.erase(it1);
}
else if(a==2){
shu.insert(++it1,c);
shu.erase(it2);
}
else if(a==3){
swap(it1,it2);
}
else if(a==4){
// reverse(shu.begin(),shu.end());
// shu.reverse();
re++;
}
}
long long sum=0;
if(n%2==1){
long long ss=n/2+1;
sum=ss*ss;
}
else if(re%2==0){
long long tt=n/2;
sum=tt*tt;
}
else if(re%2==1){
long long rr=n/2;
sum=rr*(rr+1);
}
printf("Case %d: %lld\n",ti,sum);
// cout<<"Case "<<ti<<": "<<sum<<endl;
}
return 0;
}
备文
#define LL long long
#define ULL unsigned long long
#define mod 1000000007
#define eps 1e-8
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
const int N=100005;
八大A+B格式
边界数问题,容错性
少要递归，用存数组。
Cin cout scanf()printf() puts(s) gets(s) c=getchar() putchar(c)
While((c=getchar())!=’\n’)，for(int i=0;s[i]!=’\0’;i++)注意’\n’和’\0’;or i<strlen(s);
Strcoy strcat，尽量引有的函数
For()for()数比数
空格在之前还是在之后/
大数组定义在main外,要定义大一些，调用function不要定义返回的数组
引用是c++的
Scanf的Double %lf，定义尽量不要float,精度问题
Double除，记得加点
打表
#define f(x) (x*x+2*x)
秦九韶算法
If else if
__int64 %64I
Long long %.0f
c -std=c99 随地定义
注意初始化{}内外，int a[100]={0};
I*i<=n i<=sqrt(n)
及时break for(i=2;i<=sqrt(a);i++) if(a%i==0){f=0;break;}
While(*a++=*b++)与while(a[i++]=b[i])，++在[]还是在外
While()for()
边输边算
Return n==1？1：n*f（n-1）
if（!a）if(a==0)哪好
Struct
3!+6！+91+12！+15！+18!+21！
-‘a’+’A’==97-65=32
‘ ‘== 32 ‘0’==48 Tab==9 ,13‘\n’,‘\0’
只求结果，time,过程
Q: 为什么我的程序在自己的电脑上正常编译，而系统告诉我编译错误！
A:
|
C: |
gcc Main.c -o Main -02 -Wall -lm --static -std=c99 -DONLINE_JUDGE |
|
|
C++: |
g++ Main.cc -o Main -02 -Wall -lm --static -DONLINE_JUDGE |
|
|
Pascal: |
fpc Main.pas -oMain -01 -Co -Cr -Ct -Ci |
|
|
Java: |
javac -J-Xms32m -J-Xmx256m Main.java * Java has 2 more seconds and 512M more memory when running and judging. |
|
GCC的编译标准与VC6有些不同，更加符合c/c++标准：
o (1) main 函数必须返回int, void main 的函数声明会报编译错误。
o (2) i 在循环外失去定义 "for(int i=0...){...}"
o (3) itoa 不是ansi标准函数。
o (4) __int64 不是ANSI标准定义，只能在VC使用，但是可以使用long long声明64位整数。
Q: 系统返回信息都是什么意思？
A:
详见下述：
等待 : 系统忙，你的答案在排队等待。
等待重判 : 因为数据更新或其他原因，系统将重新判你的答案。
编译中 : 正在编译。
运行并评判 : 正在运行和判断。
正确 : 程序通过！
格式错误 : 答案基本正确，但是格式不对。
答案错误 : 答案不对，仅仅通过样例数据的测试并不一定是正确答案，一定还有你没想到的地方。
时间超限 : 运行超出时间限制，检查下是否有死循环，或者应该有更快的计算方法。
内存超限 : 超出内存限制，数据可能需要压缩，检查内存是否有泄露。
输出超限 : 输出超过限制，你的输出比正确答案长了两倍。
运行错误 : 运行时错误，非法的内存访问，数组越界，指针漂移，调用禁用的系统函数。
编译错误 : 编译错误，请点击后获得编译器的详细输出。
C++中的long long和__int64类型
2011-05-05 17:02:50| 分类： C C++学习|举报|字号 订阅
C++中的long long和__int64类型 （转载）
C语言中long long的用法
http://www.awuit.com/c-language-the-usage-of-long-long/
在分析BT代码的过程中，遇到了这样的定义:long long line_position;很是纳闷，在C语言中我还没有见过这样的写法，网上搜了，资料也很少，最后在C语言标准与实现这本书中找到了关于long long的说法。在C语言的C99标准扩展了新的整数类型 long long，long是32位宽，占4个字节，long long通常被定义成 64 位宽，也就可以实现了在32位机器上可以扩展8字节的数据，GUN C也支持，当然在64位平台上就存在这个问题了。C99标准并没有硬性规定具体到某种平台上的某种整数类型究竟占用多少字节、能够表示多大范围的数值等，只是给出一条原则和一个参考数值集合，只要同时满足这两方面条件就算是符合 C 标准。
之后，我查看了C99标准：
—The rank of long long int shall be greater than the rank of long int,which
shall be greater than the rank of int,which shall be greater than the rank of short
int,which shall be greater than the rank of signed char.
意思是说：
long long 的级别高于 long ，long 的级别高于 int ，int 的级别高于 short ，short 的级别高于 char 。（另外有 _Bool 永远是最低级别）。级别高的整数类型的宽度大于等于级别较低的整数类型。
编译long long需要支持C99标准的编译器才行，VC并不支持，但有对应的类型__int64
C++ __int64用法
http://341871.blog.51cto.com/331871/71253
在做ACM题时，经常都会遇到一些比较大的整数。而常用的内置整数类型常常显得太小了：其中long 和 int 范围是[-2^31,2^31)，即-2147483648~2147483647。而unsigned范围是[0,2^32)，即0~4294967295。也就是说，常规的32位整数只能够处理40亿以下的数。
那遇到比40亿要大的数怎么办呢？这时就要用到C++的64位扩展了。不同的编译器对64位整数的扩展有所不同。基于ACM的需要，下面仅介绍VC6.0与g++编译器的扩展。
VC的64位整数分别叫做__int64与unsigned __int64，其范围分别是[-2^63, 2^63)与[0,2^64)，即-9223372036854775808~9223372036854775807与0~18446744073709551615(约1800亿亿)。对64位整数的运算与32位整数基本相同，都支持四则运算与位运算等。当进行64位与32位的混合运算时，32位整数会被隐式转换成64位整数。但是，VC的输入输出与__int64的兼容就不是很好了，如果你写下这样一段代码：
那么，在第2行会收到“error C2679: binary '>>' : no operator defined which takes a right-hand operand of type '__int64' (or there is no acceptable conversion)”的错误；在第3行会收到“error C2593: 'operator <<' is ambiguous”的错误。那是不是就不能进行输入输出呢？当然不是，你可以使用C的写法：
scanf("%I64d",&a);
printf("%I64d",a);
就可以正确输入输出了。当使用unsigned __int64时，把"I64d"改为"I64u"就可以了。
OJ通常使用g++编译器。其64位扩展方式与VC有所不同，它们分别叫做long long 与 unsigned long long。处理规模与除输入输出外的使用方法同上。对于输入输出，它的扩展比VC好。既可以使用
cin>>a;
3 cout<<a;
也可以使用
scanf("%lld",&a);
printf("%lld",a);
最后我补充一点：作为一个特例，如果你使用的是Dev-C++的g++编译器，它使用的是"%I64d"而非"%lld"。
把Linux的东西移植到Windows 下， 问题真是多， 有时候感觉很是奇怪！ 今天有遇到了一个！
__int64在 Windows下怎么输出的问题？ 我还以为是强制转换的时候出问题了， 查了好长时间！
下面是测试代码， 已经通过Windws, Linux两个平台的测试了！
#include <stdio.h>
#ifdef _WIN32
typedef unsigned __int64 uint64_t;
#else
typedef unsigned long long uint64_t;
#endif
typedef unsigned int uint32_t;
typedef unsigned short uint16_t;
typedef unsigned char uint8_t;
int main(int argc, char *argv[])
{
uint32_t t321, t322, t323;
uint64_t t641, t642, t643;
uint8_t *p;
uint8_t t[64] =
{
0x4E, 0x7C, 0x00, 0x00, 0x00, 0x00,
0x4E, 0x7C, 0x00, 0x00, 0x00, 0x00,
0x04, 0x00, 0x00, 0x00, 0x00, 0x00
};
printf(
"sizeof(uint64_t) = %d\n"
"sizeof(uint32_t) = %d\n"
, sizeof(uint64_t), sizeof(uint32_t));
p = t;
t321 = *(uint32_t *)p; p += 6;
t322 = *(uint32_t *)p; p += 6;
t323 = *(uint32_t *)p; p += 6;
printf("t321[%X].%d t322[%X].%d t323[%X].%d\n"
, t321, t321, t322, t322, t323, t323);
p = t;
t641 = *(uint32_t *)p; p += 6;
t642 = *(uint32_t *)p; p += 6;
t643 = *(uint32_t *)p; p += 6;
#ifdef _WIN32
printf("t641[%I64X].%I64d t642[%I64X].%I64d t643[%I64X].%I64d\n"
, t641, t641, t642, t642, t643, t643);
#else
printf("t641[%llX].%lld t642[%llX].%lld t643[%llX].%lld\n"
, t641, t641, t642, t642, t643, t643);
#endif
t641 = 0x1122334455667788;
#ifdef _WIN32
printf("%I64X %I64d \n", t641, t641);
#else
printf("%llX %lld \n", t641, t641);
#endif
return 0;
}
/*
Test Env:
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86
Microsoft Windows 2000 [Version 5.00.2195]
Result:
sizeof(uint64_t) = 8
sizeof(uint32_t) = 4
t321[7C4E].31822 t322[7C4E].31822 t323[4].4
t641[7C4E].31822 t642[7C4E].31822 t643[4].4
1122334455667788 1234605616436508552
--------------------------------------
Test Env:
gcc version 3.2.3 20030502 (Red Hat Linux 3.2.3-47.3)
Result:
sizeof(uint64_t) = 8
sizeof(uint32_t) = 4
t321[7C4E].31822 t322[7C4E].31822 t323[4].4
t641[7C4E].31822 t642[7C4E].31822 t643[4].4
1122334455667788 1234605616436508552
*/
在进行移植的时候可能用的上的：
#ifdef _WIN32
# define APR_UINT64_T_HEX_FMT "llx"
#else
# define APR_UINT64_T_HEX_FMT "I64x"
#endif
example:
sprintf(buf, "%" APR_UINT64_T_HEX_FMT, var);
#define HOST_WIDEST_INT_PRINT_DEC "%I64d"
#define HOST_WIDEST_INT_PRINT_UNSIGNED "%I64u"
#define HOST_WIDEST_INT_PRINT_HEX "0x%I64x"
发表于： 2007-10-18，修改于： 2007-10-18 16:21
引文来源 C++中的long long和__int64类型
1098并归排序
#include <stdio.h>
#include <stdlib.h>
int a[500001],t[500001];
long long sum;
void Merge(int l,int m,int r){
int p=0, i=l,j=m+1;
while(i<=m&&j<=r) {
if(a[i]>a[j]) { t[p++]=a[j++]; sum+=m-i+1; }
else t[p++]=a[i++]; }
while(i<=m) t[p++]=a[i++];
while(j<=r) t[p++]=a[j++];
for(i=0;i<p;i++) a[l+i]=t[i];
}
void MergeSort(int l,int r){
int m;
if(l<r) {
m=(l+r)/2;
MergeSort(l,m);
MergeSort(m+1,r);
Merge(l,m,r); }
}
int main(){
int n,i;
while(scanf("%d",&n)!=EOF,n) {
sum=0;
for(i=0;i<n;i++) scanf("%d",&a[i]);
MergeSort(0,n-1);
printf("%lld\n",sum);
}
return 0;
}
1281字符串间的比较
#include <iostream>
#include<cstring>
using namespace std;
char s[22],str[22][22];
int main() {
int a;
cin>>a;
for(int i=0;i<=a;i++)////
//cin.getline(str[i],'\n');
gets(str[i]);
for(int i=0;i<=a-1;i++)///
for(int j=0;j<=a-1-i;j++)////
if(strcmp(str[j],str[j+1])>0)
{
strcpy(s,str[j]);
strcpy(str[j],str[j+1]);
strcpy(str[j+1],s);
}
for(int i=1;i<=a;i++)////
cout<<str[i]<<endl;
return 0;
}