Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
很简单的一道题，注意ll的数据溢出，可以先打个表，16数据就会溢出，所有只要判断到15
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const int N = 3005;
ll n;
ll k;
int main()
{
ios_base::sync_with_stdio(false);
// freopen("data.txt","r",stdin);
while(cin >> n)
{
ll ct =0;
for(int i=1;i<=15;i++)
{
ll t = qpow(i,i);
// cout<<t<<" "<<i<<endl;
if(t>n)
{
break;
}
ct++;
}
cout <<ct<<endl;
}
return 0;
}
Covering
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 439 Accepted Submission(s): 214
Problem Description
Bob's school has a big playground, boys and girls always play games here after school.
To protect boys and girls from getting hurt when playing happily on the playground, rich boy Bob decided to cover the playground using his carpets.
Meanwhile, Bob is a mean boy, so he acquired that his carpets can not overlap one cell twice or more.
He has infinite carpets with sizes of 1×2 and 2×1, and the size of the playground is 4×n.
Can you tell Bob the total number of schemes where the carpets can cover the playground completely without overlapping?
To protect boys and girls from getting hurt when playing happily on the playground, rich boy Bob decided to cover the playground using his carpets.
Meanwhile, Bob is a mean boy, so he acquired that his carpets can not overlap one cell twice or more.
He has infinite carpets with sizes of 1×2 and 2×1, and the size of the playground is 4×n.
Can you tell Bob the total number of schemes where the carpets can cover the playground completely without overlapping?
Input
There are no more than 5000 test cases.
Each test case only contains one positive integer n in a line.
1≤n≤1018
Each test case only contains one positive integer n in a line.
1≤n≤1018
Output
For each test cases, output the answer mod 1000000007 in a line.
Sample Input
1 2
Sample Output
1 5
Source
Recommend
liuyiding
这个是队友想出来的，先推出一个公式，然后用矩阵快速幂直接过
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define LL long long
const int mod=1000000007;
struct matrix
{
LL x[4][4];
};
matrix mutimatrix(matrix a,matrix b)
{
matrix temp;
memset(temp.x,0,sizeof(temp.x));
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
for(int k=0;k<4;k++)
{
temp.x[i][j]+=a.x[i][k]*b.x[k][j];
temp.x[i][j]%=mod;
}
return temp;
}
matrix k_powmatrix(matrix a,LL n)
{
matrix temp;
memset(temp.x,0,sizeof(temp.x));
for(int i=0;i<4;i++)
temp.x[i][i]=1;
while(n)
{
if(n&1)
temp=mutimatrix(temp,a);
a=mutimatrix(a,a);
n>>=1;
}
return temp;
}
int main()
{
int T;
LL n;
while(scanf("%lld",&n)!=EOF)
{
if(n==1)
{
printf("1\n");
continue;
}
if(n==2)
{
printf("5\n");
continue;
}
if(n==3)
{
printf("11\n");
continue;
}
if(n==4)
{
printf("36\n");
continue;
}
matrix st;
memset(st.x,0,sizeof(st.x));
st.x[0][0]=1;
st.x[1][0]=5;
st.x[2][0]=1;
st.x[3][0]=-1;
st.x[0][1]=1;
st.x[1][2]=1;
st.x[2][3]=1;
matrix init;
memset(init.x,0,sizeof(init.x));
init.x[0][0]=36;
init.x[0][1]=11;
init.x[0][2]=5;
init.x[0][3]=1;
st=k_powmatrix(st,n-4);
st=mutimatrix(init,st);
//for(int i=0;i<4;i++)
printf("%lld\n",(st.x[0][0]+mod)%mod);
}
return 0;
}
/*
|f[n] f[n-1]|*|a 1|=|f[n+1] f[n]|
|b 0|
*/
CS Course
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 547 Accepted Submission(s): 267
Problem Description
Little A has come to college and majored in Computer and Science.
Today he has learned bit-operations in Algorithm Lessons, and he got a problem as homework.
Here is the problem:
You are giving n non-negative integers a1,a2,⋯,an, and some queries.
A query only contains a positive integer p, which means you
are asked to answer the result of bit-operations (and, or, xor) of all the integers except ap.
Today he has learned bit-operations in Algorithm Lessons, and he got a problem as homework.
Here is the problem:
You are giving n non-negative integers a1,a2,⋯,an, and some queries.
A query only contains a positive integer p, which means you
are asked to answer the result of bit-operations (and, or, xor) of all the integers except ap.
Input
There are no more than 15 test cases.
Each test case begins with two positive integers n and p
in a line, indicate the number of positive integers and the number of queries.
2≤n,q≤105
Then n non-negative integers a1,a2,⋯,an follows in a line, 0≤ai≤109 for each i in range[1,n].
After that there are q positive integers p1,p2,⋯,pqin q lines, 1≤pi≤n for each i in range[1,q].
Each test case begins with two positive integers n and p
in a line, indicate the number of positive integers and the number of queries.
2≤n,q≤105
Then n non-negative integers a1,a2,⋯,an follows in a line, 0≤ai≤109 for each i in range[1,n].
After that there are q positive integers p1,p2,⋯,pqin q lines, 1≤pi≤n for each i in range[1,q].
Output
For each query p, output three non-negative integers indicates the result of bit-operations(and, or, xor) of all non-negative integers except
ap in a line.
Sample Input
3 3 1 1 1 1 2 3
Sample Output
1 1 0 1 1 0 1 1 0
Source
Recommend
liuyiding
利用位运算的特性，先统计一些所有数的相同位的和，然后再进行判断
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const int N = 100005;
int sum[35];
int n,q;
bool dig[N][35];
int a[N];
int t;
int ans[N][3];
int vis[N];
ll er[35];
//int ans[N][3];
int main()
{
// ios_base::sync_with_stdio(false);
// freopen("data.txt","r",stdin);
er[0] = 1;
for(int i=1;i<35;i++)
{
er[i] = 2*er[i-1];
}
while(~scanf("%d%d",&n,&q))
{
memset(sum,0,sizeof(sum));
memset(ans,0,sizeof(ans));
memset(dig,0,sizeof(dig));
memset(vis,0,sizeof(vis));
memset(a,0,sizeof(a));
int max_dig = 0;
for(int i=0;i<n;i++)
{
int ind=0;
scanf("%d",&t);
a[i] = t;
while(t)
{
dig[i][ind++] = t%2;
t/=2;
}
max_dig = max(max_dig,ind);
}
for(int i=0;i<n;i++)
{
for(int j = 0 ;j < max_dig;j++)
{
sum[j] += dig[i][j];
}
}
int ans1,ans2,ans3;
for(int i = 0;i<q;i++)
{
ans1 = ans2 = ans3 = 0;
scanf("%d",&t);
t--;
if(vis[t])
{
printf("%d %d %d\n",ans[t][0],ans[t][1],ans[t][2]);
continue;
}
vis[t] = 1;
for(int j = 0;j<max_dig;j++)
{
if(dig[t][j]==0&&sum[j]==n-1)
{
ans[t][0] += er[j];
}
if(dig[t][j]==1&&sum[j]==n)
{
ans[t][0] += er[j];
}
}
for(int j = 0;j<max_dig;j++)
{
if(dig[t][j]==0&&sum[j])
{
ans[t][1] += er[j];
}
if(dig[t][j]==1&&sum[j]>1)
{
ans[t][1] += er[j];
}
}
for(int j = 0;j<max_dig;j++)
{
if(dig[t][j]==0&&sum[j]%2==1)
{
ans[t][2] += er[j];
}
if(dig[t][j]==1&&(sum[j]-1)%2==1)
{
ans[t][2] += er[j];
}
}
printf("%d %d %d\n",ans[t][0],ans[t][1],ans[t][2]);
}
}
return 0;
}
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
贪心，先把对子给算减去，奇数留1个，偶数留两个，然后考虑下面这几种情况
1 2 3 3 4 5
1 1 2 2 3 3
1 2 2 3 3
然后遍历一遍就可求解了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const int N = 1000005;
int n;
int a[N];
int num[N];
int main()
{
// ios_base::sync_with_stdio(false);
// freopen("data.txt","r",stdin);
// freopen("data.txt","w",stdout);
while(scanf("%d",&n)!=EOF)
{
ll ct = 0;
memset(num,0,sizeof(num));
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
num[a[i]]++;
}
for(int i=1;i<=n;i++)
{
if(num[i]==0) continue;
if(num[i]%2)
{
ct += num[i]/2;
num[i]=1;
}
else
{
ct += (num[i]-2)/2;
num[i]=2;
}
}
for(int i=1;i<=n;i++)
{
if(num[i]==2)
{
ct++;
num[i]=0;
}
else
{
if(num[i]==1&&num[i+1]==1&&num[i+2])
{
ct++;
num[i]--;
num[i+1]--;
num[i+2]--;
}
}
}
printf("%I64d\n",ct);
}
return 0;
}