正负数判断
内存限制: 256 Mb ?时间限制: 1000 ms
题目描述
给定一个整数 n，若 n 为正数，输出 Positive，若 n 为负数，输出 Negative，若 n 恰好为零，输出 Zero。
输入格式
单个整数：表示给定的 n。
输出格式
按照描述输出结果
数据范围
?1,000,000≤n≤1,000,000
样例数据
输入:
100
输出:
Positive
输入:
-9
输出:
Negative
输入:
0
输出:
Zero
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main()
{
int n;
cin>>n;
if(n>0)cout<<"Positive"<<endl;
else if(n<0)cout<<"Negative"<<endl;
else cout<<"Zero"<<endl;
return 0;
}打印沙漏
内存限制: 256 Mb ?时间限制: 1000 ms
题目描述
给定一个整数 n，请打印出一个 2n?1 行的沙漏，例如当 n=3 时，输出
*****
?***
? *
?***
*****
输入格式
单个整数：表示图形的大小参数 n。
输出格式
共 2n?1 行：表示一个沙漏形状的图形。
数据范围
2≤n≤50
样例数据
输入:
2
输出:
***
?*
***
输入:
4
输出:
*******
?*****
? ***
? ?*
? ***
?*****
*******
?
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main()
{
int n;
cin>>n;
int m=n*2-1;
for(int i=0;i<n;i++){
for(int j=1;j<=i;j++) cout<<" ";
for(int j=1;j<=m;j++) cout<<"*";
cout<<endl;
m-=2;
}
m+=2;
for(int i=n-2;i>=0;i--){
m+=2;
for(int j=1;j<=i;j++) cout<<" ";
for(int j=1;j<=m;j++) cout<<"*";
cout<<endl;
}
return 0;
}逻辑求值
内存限制: 256 Mb ?时间限制: 1000 ms
题目描述
逻辑表达式的定义如下：
单个 true 或 false 都是逻辑表达式；
如果 S 及 T 是逻辑表达式，那么 S and T 也是逻辑表达式；
如果 S 及 T 是逻辑表达式，那么 S or T 也是逻辑表达式。
对逻辑表达式求值前，需要确定 and 与 or 运算的优先级：
若规定先算 and 再算 or，则以下表达式的值为
? true or false and false or false
? ? ? ? ? ~~~~~~~~~~~~~~~ ??
= true or false or false
= true
定义这种计算顺序为合取优先；
若规定先算 or 再算 and，则以下表达式的值为
? true or false and false or false
? ~~~~~~~~~? ? ? ? ~~~~~~~~~~
= true and false
= false
定义这种计算顺序为析取优先。
给定一个逻辑表达式，请分别求出合取优先及析取优先规定下的计算结果。
输入格式
一串字符序列：表示给定的逻辑表达式，保证输入数据是一个合法的逻辑表达式。
输出格式
第一行：表示在合取优先规定下逻辑表达式的值。
第二行：表示在析取优先规定下逻辑表达式的值。
数据范围
记 n 表示输入字符序列的总长度，
对于 50% 的数据，1≤n≤1000；
对于 100% 的数据，1≤n≤1,000,000。
样例数据
输入:
true or false and false or false
输出:
true
false
?
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <stack>
using namespace std;
string s;
stack<string> a1,b1;
stack<string> a2,b2;
int main()
{
while(cin>>s){
if(s=="true"||s=="false") {
if(a1.empty()) a1.push(s);
else if(b1.top()=="and"){
string a=a1.top();
if(a=="true"&&s=="true"){
a1.pop();b1.pop();
a1.push("true");
}
else{
a1.pop();b1.pop();
a1.push("false");
}
}
else a1.push(s);
}
else b1.push(s);
if(s=="true"||s=="false") {
if(a2.empty()) a2.push(s);
else if(b2.top()=="or"){
string a=a2.top();
if(a=="true"||s=="true"){
a2.pop();b2.pop();
a2.push("true");
}
else{
a2.pop();b2.pop();
a2.push("false");
}
}
else a2.push(s);
}
else b2.push(s);
}
while(!b1.empty()){
string a=a1.top();a1.pop();
string b=a1.top();a1.pop();
if(a=="true"||b=="true") a1.push("true");
else a1.push("false");
b1.pop();
}
cout<<a1.top()<<endl;
while(!b2.empty()){
string a=a2.top();a2.pop();
string b=a2.top();a2.pop();
if(a=="true"&&b=="true") a2.push("true");
else a2.push("false");
b2.pop();
}
cout<<a2.top()<<endl;
return 0;
}三扔硬币
内存限制: 256 Mb ?时间限制: 1000 ms
题目描述
扔 n 次硬币的结果可以用一串 0/1 序列来表示。给定 n，请统计有多少种扔硬币的结果中不含三个连续的 0 且不含三个连续的 1。
当 n 较大的时候，答案可能很大，所以输出答案模 1,000,000,007 的余数即可。
输入格式
单个整数：表示 n。
输出格式
单个整数：表示答案模 1,000,000,007 的余数。
数据范围
对于 30% 的数据，1≤n≤20；
对于 60% 的数据，1≤n≤5000；
对于 100% 的数据，1≤n≤1,000,000。
样例数据
输入:
3
输出:
6
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
long long a[1000005]={0,2,4,6};
int main()
{
int n;
cin>>n;
if(n<4) {
cout<<a[n]; return 0;
}
for(int i=4;i<=n;i++){
a[i]=(a[i-2]*2%1000000007+a[i-3])%1000000007;
}
cout<<a[n]<<endl;
return 0;
}洗牌
内存限制: 256 Mb ?时间限制: 1000 ms
题目描述
给定一个整数 n，表示 n 张牌，牌的编号为 1 到 n。
再给定一个洗牌置换 f1,f2 ,…,fn ，进行一次洗牌操作时，应将第一号位置的牌交换到第 f1号位置，将第 i?号位置的牌交换到第 fi号位置。保证 f 是一个 1 到 n 的排列（即 1 到 n 中的每个数字出现且只出现一次）。
一开始，牌的顺序为 1,2,?,n。给定一个整数 k，请输出经过 k 次洗牌后牌的顺序。
输入格式
第一行：两个整数 n?与 k；
第二行：n?个整数表示 f1,f2, ... ,fn
输出格式
单独一行：n 个整数表示洗 k 次牌后的顺序。
数据范围
对于 30% 的数据，1≤n≤100，1≤k≤1000；
对于 60% 的数据，1≤n≤1000，1≤k≤10,000；
对于 100% 的数据，1≤n≤100,000，1≤k≤1,000,000,000。
样例数据
输入:
4 2
4 1 2 3
输出:
3 4 1 2
说明:
1234-->2341-->3412
输入:
3 100000
1 2 3
输出:
1 2 3
说明:
每次洗牌都不会改变牌的位置
//代码超时
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int a[100005];
int b[100005];
int c[100005];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
a[i]=i;
cin>>b[i];
}
//k%=n;
for(int j=1;j<=k;j++){
for(int i=1;i<=n;i++){
c[b[i]]=a[i];
}
copy(begin(c),end(c),begin(a));
memset(c,0,sizeof(c));
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+5;
int jump[N][31];//jump[i][j]第i位置上的牌，跳跃2^j后到达的位置
int n,k;
int ans[N];
int main()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&jump[i][0]);//i->f_i 2^0=1
for(int j=1;j<=30;j++)
for(int i=1;i<=n;i++)
jump[i][j]=jump[jump[i][j-1]][j-1];
for(int i=1;i<=n;i++){
int x=i;
for(int j=0;j<=30;j++)
if(k&(1<<j)) x=jump[x][j];
ans[x]=i;
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
/*
题解：倍增思想
首先我们需要明白牌与牌之间在变换过程中是互不影响的，
然后我们可以考虑使用倍增算法来加速每张牌的变换。
具体的，我们设jump[i][j]表示将第i个位置的牌变换2^j次后到哪个位置。
显然有jump[i][j]=jump[jump[i][j-1]][j-1]
于是我们只需要枚举每一个位置，然后对k进行二进制拆位加速变换即可。
*/
