2017ACM/ICPC广西邀请赛-重现赛(感谢广西大学)
上一场CF打到心态爆炸,这几天也没啥想干的
A Math Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Each case only contains a positivse integer n in a line.
1≤n≤1018
4
2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=;
int main()
{
ll n;
while(~scanf("%lld",&n))
{
if(n>=N)
printf("15\n");
else
{
for(int k=; k<; k++)
{
ll s=;
for(int i=; i<k; i++)
s*=k;
if(s>n)
{
printf("%d\n",k-);
break;
}
}
}
}
return ;
}
Covering
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
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?
Each test case only contains one positive integer n in a line.
1≤n≤1018
2
5
a[n]=a[n-1]+5*a[n-2]+a[n-3]-a[n-4];
#include <stdio.h>
#include <string.h>
const int MD=1e9+;
typedef long long LL;
struct matrix
{
LL mat[][];
};
matrix matmul(matrix a,matrix b,int n)
{
int i,j,k;
matrix c;
memset(c.mat,,sizeof(c.mat));
for(i=; i<n; i++)
{
for(j=; j<n; j++)
{
for(k=; k<n; k++)
{
c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MD;
}
}
}
return c;
}
matrix matpow(matrix a,LL k,int n)
{
matrix b;
int i;
memset(b.mat,,sizeof(b.mat));
for(i=; i<n; i++) b.mat[i][i]=;
while(k)
{
if(k&) b=matmul(a,b,n);
a=matmul(a,a,n);
k>>=;
}
return b;
}
int main()
{
LL k;
matrix a,b;
memset(a.mat,,sizeof(a.mat));
memset(b.mat,,sizeof(b.mat));
a.mat[][]=,a.mat[][]=,a.mat[][]=;
b.mat[][]=,b.mat[][]=,b.mat[][]=,b.mat[][]=-;
b.mat[][]=,b.mat[][]=,b.mat[][]=;
while(~scanf("%lld",&k))
{
printf("%lld\n",(matmul(matpow(b,k,),a,).mat[][]+MD)%MD);
}
return ;
}
CS Course
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
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.
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].
1 1 1
1
2
3
1 1 0
1 1 0
异或最简单,再异或一次就好了
所以按位存储了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+;
int a[N],b[N];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(b,,sizeof(b));
int Xor=,And=0xffffffff,Or=;
for(int i=; i<=n; i++)
{
int x;
scanf("%d",&x);
a[i]=x;
And&=x;
Or|=x;
Xor^=x;
for(int j=; x; j++,x>>=)
b[j]+=x%;
}
while(m--)
{
int q;
scanf("%d",&q);
q=a[q];
int A=And,O=Or,X=Xor;
X=X^q;
for(int j=; j<=; j++,q>>=)
{
if(b[j]==n-&&q%==)A+=(<<j);
if(b[j]==&&q%)O-=(<<j);
}
printf("%d %d %d\n",A,O,X);
}
}
return
Duizi and Shunzi
Now give you n integers, ai(1≤i≤n)ai(1≤i≤n)
We define two identical numbers (eg: 2,22,2) a Duizi,
and three consecutive positive integers (eg: 2,3,42,3,4) a Shunzi.
Now you want to use these integers to form Shunzi and Duizi as many as possible.
Let s be the total number of the Shunzi and the Duizi you formed.
Try to calculate max(s)max(s).
Each number can be used only once.
InputThe input contains several test cases.
For each test case, the first line contains one integer n(1≤n≤1061≤n≤106).
Then the next line contains n space-separated integers aiai (1≤ai≤n1≤ai≤n)
OutputFor each test case, output the answer in a line.
Sample Input
7
1 2 3 4 5 6 7
9
1 1 1 2 2 2 3 3 3
6
2 2 3 3 3 3
6
1 2 3 3 4 5
Sample Output
2
4
3
2
Hint
Case 1(1,2,3)(4,5,6) Case 2(1,2,3)(1,1)(2,2)(3,3) Case 3(2,2)(3,3)(3,3) Case 4(1,2,3)(3,4,5)
这个题看起来很简单,问你最多可形成多少个对子和顺子
可是有坑啊,可以按照对子打,也可以按照顺子打,我当然按照对子打了,但是按照对子打可能我的顺子就没了,所以我首先是要打足够多的牌
比如我往下贪心的时候,如果第二张恰好是对子,我贪心就亏了,但是我下一张正好三张我肯定就要了这个顺子
所以就是记录顺子和找对子了
#include <stdio.h>
#include <string.h>
const int N=1e5+;
int a[N];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(a,,sizeof(int)*(n+));
for(int i=; i<n; i++)
{
int x;
scanf("%d",&x);
a[x]++;
}
int ans=;
for(int i=; i<n-; i++)
{
ans+=a[i]/;
if(a[i]&&&a[i+]&&&a[i+])
{
ans++;
a[i+]--;
a[i+]--;
}
}
ans+=a[n-]/+a[n]/;
printf("%d\n",ans);
}
return ;
}
最新文章
- DataTime格式化大全(转载)
- Oracle数据库11g基于rehl6.5的配置与安装
- IDEA UML类图插件
- linux环境进程的停止
- 百度编辑器ueditor代码高亮效果前台不显示的解决方法
- 关于Linux的总结(二)
- 2.1CUDA-Thread
- iOS UICollectionView基础
- Android 不能勾选 Project Build Target
- javabean+servlet+jsp程序_个人辛苦探索
- MVC4中 jquery validate 不用submit方式验证表单或单个元素
- 手势(Gesture)的增加和识别
- mysql中国的内容php网页乱码问题
- [CLR via C#]1.2 将托管模块合并成程序集
- MySQL-8.0.11与Navicat Premium安装教程
- laravel5.3安装redis扩展包
- GO语言的进阶之路-面向对象编程
- python - classs内置方法 solt
- oracle中主键自增
- python二进制转换
热门文章
- 本机运行x程序出现:Can&#39;t open display 原因及其解决方法(貌似非永久)
- Git服务器和Git权限管理应用GITLAB安装方法
- 理想路径——双向BFS
- 120. Triangle 以及一个多维vector如何初始化
- 如何在Mac OS X中开启或关闭显示隐藏文件命令
- js中声明函数的三种方式
- Python基础篇 -- 运算符和编码
- PAT (Advanced Level) Practise - 1098. Insertion or Heap Sort (25)
- jquery操作滚动条滚动到指定元素位置 scrollTop
- 低性能3张图片轮播React组件