2 石头剪刀布 #
就三种情况，甚至可以直接判断录入字符串的首字母是什么来输出
#include <iostream>
using namespace std;
int main()
{
string s;
cin >>s;
if(s=="shitou") cout << "bu" << endl;
else if(s=="jiandao") cout << "shitou" << endl;
else if(s=="bu") cout << "jiandao" << endl;
return 0;
}
a=input()
if a=='bu':
print("jiandao")
if a=='shitou':
print("bu")
if a=='jiandao':
print("shitou")
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.nextLine();
if(s.equals("shitou")) {
System.out.print("bu");
}
if(s.equals("bu")) {
System.out.print("jiandao");
}
if(s.equals("jiandao")) {
System.out.print("shitou");
}
}
}
3 斐波那契数列 #
原理都一样（dp），用数组来记录每种情况，f[1]=1,f[2]=1, f[i] = f[i-1] + f[i-2];
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long []arr = new long[61];
arr[0]=0;
arr[1]=1;
for(int i=2;i<61;i++){
arr[i]=arr[i-1]+arr[i-2];
}
System.out.println(arr[n]);
}
}
list=[0 for i in range(61)]
list[1]=1
n=int(input())
for i in range(2,n+1):
list[i]=list[i-1]+list[i-2]
print(list[n])
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100],n;
int main(){
cin>>n;
a[2]=1;
a[1]=1;
for(int i=3;i<100;i++){
a[i]=a[i-1]+a[i-2];
}
cout<<a[n];
}
4 时间转换 #
除法运算直接去余数，t/3600就是x小时，t%3600就是去掉x个小时剩下的时间，（t%3600）/60就是y分钟，（t%3600）%60就是去掉x个小时y分钟剩下的时间，可以化简为t%60。
#include<stdio.h>
int main(){
int a,b,c,d,e;
scanf("%d",&a);
b=a/3600;
c=a%3600;
d=c/60;
e=c%60;
printf("%d %d %d",b,d,e);
return 0;
}
a=int(input())
b=int(a/3600)
c=int((a%3600)/60)
d=a%60
print(b,c,d)
import java.util.*;
public class Main{
public static void main(String arg[]){
Scanner input = new Scanner(System.in);
int time = input.nextInt();
int s=time%60;
int h=time/3600;
int m=(time-h*3600-s)/60;
System.out.println(h+" "+m+" "+s);
}
}
5 数独 #
每行包含从 1到 9 的每个数字，每个数字一次。 每列包含从 1到9 的每个数字，每个数字一次。 将 9x9 矩阵划分为 9 个非重 3x3 子矩阵。每个子矩阵包含从 1到 9 的每个数字，每个数字一次。样例肯定是有漏洞的（不用判断九宫也过）。 数独必须把每种情况求出来，下面这个九宫每行每列都满足，但九宫不满足。 下面c++代码有详解，java的只特判了第一宫。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[15][15],T,n=9;
int main(){
cin>>T;
while(T--){
int m=0;
for(int i=0;i<n;i++){
int b[15]={0};
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
b[a[i][j]]++;
if(b[a[i][j]]==2)m=1;
}
}
if(m==1){
cout<<"No\n";
continue;
}
for(int i=0;i<n;i++){
int b[15]={0};
for(int j=0;j<n;j++){
b[a[j][i]]++;
if(b[a[i][j]]==2)m=1;
}
}
if(m==1){
cout<<"No\n";
continue;
}
if(m==1){
cout<<"No\n";
continue;
}
else {
cout<<"Yes\n";
}
}
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] map = new int[9][9];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 9; k++) {
map[j][k] = sc.nextInt();
}
}
if(rowAndCol(map) && Xic(map)) {
System.out.println("Yes");
}else {
System.out.println("No");
}
}
}
static boolean rowAndCol(int[][] map) {
HashSet<Integer> setR = new HashSet<>();
HashSet<Integer> setC = new HashSet<>();
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 9; k++) {
setR.add(map[j][k]);
setC.add(map[k][j]);
}
if(setR.size() != 9 || setC.size() != 9) {
return false;
}
setR.clear();
setC.clear();
}
return true;
}
static boolean Xic(int[][] map) {
HashSet<Integer> setX = new HashSet<>();
for(int i = 0; i < 9; i+=3) {
for(int j = 0; j < 9; j += 3) {
for(int i2 = i; i2 < i + 3; i2++) {
for(int j2 = j; j2 < j + 3; j2++) {
setX.add(map[i2][j2]);
}
}
if(setX.size() != 9) {
setX.clear();
return false;
}
setX.clear();
}
}
return true;
}
}
6 因子之和 #
一个数的因子总是成对存在的
比如36的因子：
1*36,2*18,3*12,4*9,6*6
所以只要找根号n内的因子就行， 顺便把（与其相乘的另一个因子） 用n/i表示就可以解决一组因子。 只有i*i=n的时候是一个特例， 因子和（与其相乘的另一个因子）是同一个，要减去，分就拿满了。
出错原因大概有
1把因子看成质因子的；
2有忘记i*i的；
3有忘记1*n的；
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long res = 0;
for (int i = 1; i <= n / 2; i++) {
if(n % i == 0) {
res += i;
}
}
res += n;
System.out.println(res);
}
}
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N][N];
bool st[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n; cin >> n;
set<int> st;
for(int i = 1; i <= n / i; i++){
if(n % i == 0){
st.insert(i);
st.insert(n/i);
}
}
long long s = 0;
for(auto e: st){
s += e;
}
cout << s;
return 0;
}
7 方块 #
这题有多种解法。 首先每列互不干扰，所以我们只要算单独的一列的情况就可以了。m列就是m次方，如果题目的m够大，就得用快速幂解决。 单独一列: 1.dfs(实际上就是二进制)，(选择放长度为一的方块)或（放一个长度为二的方块）。放完就是一种情况。 Dfs遍历所有情况。（c++代码） 2.眼尖的人就会发现这是个斐波那契数列，直接求就完事了。（Java代码）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,sum=0,num=1;
void dfs(int n){
if(n==0)sum++;
if(n>1)dfs(n-2);
if(n>0)dfs(n-1);
}
int main(){
cin>>n>>m;
dfs(n);
for(int i=0;i<m;i++)num=num*sum;
cout<<num;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long res = 1;
if(n == 1) {
System.out.println(1);
return;
}
if(n == 2) {
for (int i = 0; i < m; i++) {
res *= n;
}
System.out.println(res);
return;
}
int[] num = new int[n];
num[0] = 1;
num[1] = 2;
for (int i = 2; i < n; i++) {
num[i] = num[i - 1] + num[i - 2];
}
for (int i = 0; i < m; i++) {
res *= num[n - 1];
}
System.out.println(res);
}
}
8 顺序 #
Python是真的好写（c用数组模拟的写麻了）
思路都大同小异，就是把数字挨个塞进去
数组模拟的话，个位数b[0]，十位数b[1]….塞进去用先最高位塞。（记录一下最高位是第几位，记得更新）可以塞完一起判断字符串是否相等，也可以边塞边判断。
n=int(input())
for i in range(n):
strs = ''
s=list(map(int,input().split()))
m=input()
t=s[0]
while(1):
strs+=str(t)
t+=1
if len(strs)>=s[1]:
break
if (m==strs[:s[1]]):
print("Yes")
else:
print("No")
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
int num = sc.nextInt();
int len = sc.nextInt();
sb.setLength(0);
for (int j = num; j <= len + num; j++) {
sb.append(j);
}
sb.setLength(len);
String s = sc.next();
if(s.equals(sb.toString())) {
System.out.println("Yes");
}else {
System.out.println("No");
}
}
}
}
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N][N];
bool st[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t; cin >> t;
while(t--){
int a, n;
cin >> a >> n;
string s, res = "";
cin >> s;
while(res.size() < n){
res += to_string(a);
a++;
}
if(res.substr(0, n) == s){
puts("Yes");
}else{
puts("No");
}
}
return 0;
}
9 魔法 #
模运算： #
一些题目的结果数据较大，会要求将输出结果进行取模，也就是给一个除数（如：\(10^9+7\)）并把余数作为结果。 在加法、减法、乘法运算中，我们可以在运算过程中取模，这与对输出结果进行取模是等价的。 下面进行“把自己的码力值\(x\)变为\(x^2+x\)，并重复a次的过程”的计算：
#define int long long//开long long
using namespace std;
const int mod=1e9+7;
int compute(int a){
int x=1;
for(int i=1;i<=a;i++){
x=(x+1)*x%mod;
}
return x;
}
逆元： #
对数值进行取模情况下进行除法运算，不能直接除，而是要用到逆元，a的逆元记为inv(a)。在实数运算中，除以一个数等于乘以这个数的倒数；在模运算中，逆元就是这个数的“倒数”。 例如，对2除以3的结果取模，就是2乘3的逆元，即2inv(3) 推广到分数，对2/3取模，就是分子乘分母的逆元，即2inv(3)。 乘了逆元之后，数据也可能会很大，记得再次取模。 费马定理：通过快速幂，我们可以方便地求逆元。inv(x)是求x的逆元的函数。
至此，我们可以算出经过多少次施法，二人的码力值的比值了。
#include<bits/stdc++.h>
#define el '\n'
#define int long long
using namespace std;
const int mod=1e9+7;
int qpow(int x,int n){//快速幂
int res=1;
while(n>0){
if(n&1) res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
int inv(int x){//求逆元
return qpow(x,mod-2);
}
int compute(int a){
int x=1;
for(int i=1;i<=a;i++){
x=(x+1)*x%mod;
}
return x;
}
void solve(){
int x,y;
int a=1,b=1;
scanf("%lld%lld",&x,&y);
if(x<y) swap(x,y);
a=compute(x),b=compute(y);
cout<<a*inv(b)%mod<<el;
}
这样多次求比值会有重复运算，导致超时，我们可以把次数对应的码力值用记录下来，把多次输入当查询，计算码力值的倍数。
由于题目有空间限制，不能直接开\(10^8\)大小的数组。我们开一个大小为\(10^6\)的数组，存储次数为一百的倍数的码力值，用余数推剩下的。例如查询2023次的码力值，先找2000对应的码力值，即mem[20]，再推剩下23次的码力值。
#include<bits/stdc++.h>
#define el '\n'
#define int long long//开long long
using namespace std;
const int mod=1e9+7;
int mem[1000001];
int qpow(int x,int n){
int res=1;
while(n>0){
if(n&1) res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
int inv(int x){
return qpow(x,mod-2);
}
void init(int a){//记录次数为一百的倍数的码力值
int x=1;
for(int i=1;i<=a;i++){
x=(x+1)*x%mod;
if(i%100==0) {
mem[i/100]=x;
}
}
}
int compute(int a,int x){//用来递推剩下的
for(int i=1;i<=a;i++){
x=(x+1)*x%mod;
}
return x;
}
signed main(){
init(1e8);
mem[0]=1;
int t;
cin>>t;
while(t--){
int x,y;
scanf("%lld%lld",&x,&y);
if(x<y) swap(x,y);
int a=compute(x%100,mem[x/100]),b=compute(y%100,mem[y/100]);
printf("%lld\n",a*inv(b)%mod);
}
}
10 跳 #
一眼bfs。 录入一张图 用队列存要遍历的点 每次遍历四个方向，每个方向走到底（或遇见#）停下， 中间的所有点放进队尾，并（标记走过，记录步数）。
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int N = 110;
int t, n, m;
int ha, la, hb, lb;
char a[N][N];
int dist[N][N];
int dir[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int bfs()
{
queue<pii> q;
memset(dist, 0x3f, sizeof dist);
q.push({ha, la});
dist[ha][la] = 0;
while(q.size()){
int x = q.front().first, y = q.front().second; q.pop();
for(int i = 0; i < 4; i++){
int tx = x + dir[i][0], ty = y + dir[i][1];
if(tx > 0 && tx <= n && ty > 0 && ty <= m && a[tx][ty] == '.' ){
if(dir[i][0] != 0){//上下
while(tx> 0 && tx <= n && a[tx][ty]=='.'&& dist[tx][ty] >= dist[x][y] + 1){
q.push({tx, ty});
dist[tx][ty] = dist[x][y] + 1;
tx += dir[i][0];//往该方向一直走
}
}else{//左右
while(ty> 0 && ty <= m && a[tx][ty]=='.'&& dist[tx][ty] >= dist[x][y] + 1){
q.push({tx, ty});
dist[tx][ty] = dist[x][y] + 1;
ty += dir[i][1];//往该方向一直走
}
}
}
}
}
return dist[hb][lb];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
cin >> ha >> la >> hb >> lb;
cout << bfs() << '\n';
}
return 0;
}
11 征服 #
本题使用BFS+小根堆 题目数据为10的5次方，使用邻接表存储这张图，敌军军队从1号岛屿开始（代码中以0为下标），相邻敌军岛屿上的军队数量小于敌军军队就会加入敌军，敌军扩大所占岛屿，使用BFS将相邻敌军的岛屿号与军队数量记录到小根堆中，以军队数量增序存储，接着判断小根堆中最少军队数量是否小于敌军，是则将扩大敌军所占岛屿，敌军数量加上这次吸收的军队数量，并将该岛屿号记录下来，重复上述操作； 每次存储相邻敌军的岛屿号与军队数量记录到小根堆中时间复杂度为（logn）重复上述操作不超过n次，总体时间复杂度为nlogn
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int h[N],ne[N*2],e[N*2],idx;
int p[N];
int n,m,res;
bool st[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
struct node{
int u,c;
bool operator <(const node &W)const{
return c>W.c;
}
};
void bfs()
{
priority_queue<node> q;
q.push({1,0});
res+=p[1];
while(q.size()){
auto t = q.top();
q.pop();
int u =t.u,d=t.c;
if(st[u]) continue;
st[u]=true;
//cout<<u<<" "<<d<<" "<<res<<endl;
if(res>d) res+=d;
else break; //找不到就停，减少时间
for(int i=h[u];i!=-1;i=ne[i])
{
int j = e[i];
if(!st[j]) q.push({j,p[j]});
}
}
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
while(m--){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++) cin>>p[i];
bfs();
cout<<res<<endl;
return 0;
}
12 旅行 #
思路是“反向并查集”
先把所有的边读入，把被攻陷的城市，和当天的旅程数，每个旅程记录起来
然后先把没有被攻陷的城市进行一次并查集
然后从最后一天旅程，从后往前推，推完之后，因为要走到上一天嘛，所以当天的沦陷城市，在上一天是没有沦陷的，那么把能和这个城市连通的点且未沦陷的城市做一次并查集
从此上述操作，再逆序输出答案
#include<bits/stdc++.h>
using namespace std;
const int N=50010,M=400010;
typedef pair<int,int>PII;
PII bian[M];// 记录连接的边、旅行的边
bool st[N];//true表示被攻陷了
int p[N];
vector<int>answer;//记录答案
vector<int>gs[N]; //第一个数是沦陷的城市 第二个数的接下来的旅程数 接下来每两个数为一次旅行
int n,m,d;
int h[M],e[M],ne[M],idx;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int find(int x)
{
if(x!=p[x])p[x]=find(p[x]);
return p[x];
}
signed main()
{
memset(h,-1,sizeof h);
for(int i=1;i<=N;i++)p[i]=i;
cin>>n>>m>>d;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
bian[i]={a,b};
add(a,b),add(b,a);
}
for(int i=1;i<=d;i++)
{
int c,q;
cin>>c>>q;
//被攻陷了
st[c]=true;
//记录被攻陷的城市
gs[i].push_back(c);
//记录旅程数和旅程
gs[i].push_back(q);
for(int j=1;j<=q;j++)
{
int x,y;
cin>>x>>y;
gs[i].push_back(x);
gs[i].push_back(y);
}
}
//先把没有被攻陷的城市 正常并查集
for(int i=1;i<=m;i++)
{
int a=bian[i].first;
int b=bian[i].second;
if(!st[a]&&!st[b])
{
if(find(a)!=find(b))
p[find(a)]=find(b);
}
}
for(int i=d;i>=1;i--)
{
int sum=0;
//获得原来被攻陷的城市 用于后面重建边
int city=gs[i][0];
st[city]=false;
//多少个旅程
int q=gs[i][1];
int j=2;
while(q--)
{
int a=gs[i][j];
int b=gs[i][j+1];
j+=2;
if(find(a)!=find(b))sum++;
}
answer.push_back(sum);
for(int j=h[city];~j;j=ne[j])
{
int j_city=e[j];
if(!st[j_city])
{
if(find(j_city)!=find(city))
{
p[find(j_city)]=find(city);
}
}
}
}
for(int i=answer.size()-1;i>=0;i--)cout<<answer[i]<<endl;
}
13 传递 #
题意：找到每个数的左使者（左边不超过自己且自己所能看到的最大值）和右使者（右边不超过自己且自己所能看到的最大值） 暴力解法： 逐个找每个数的左使者和右使者，从当前这个数h[i]开始，用左变量l 找左使者，l往左找，遇到比自己矮的判断是否要更新最大值，直到遇到比自己高的被挡住为止。 用右变量r 找右使者，r往右找，遇到比自己矮的就判断是否需要更新最大值，知道遇到比自己高的停止。 时间复杂度：O(n ^2)
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int h[N];
pair<int, int> p[N];
int main()
{
int k;
cin >> k;
for(int ti = 1; ti <= k; ti++){
int n;
cin >> n;
for(int i = 1; i <= n; i++)cin >> h[i];
cout << "Case " << ti << ":\n";
deque<int> q;
for(int i = 1; i <= n; i++){
int l = i - 1, r = i + 1, li = 0, ri = 0;
while(l > 0 && h[l] < h[i]){
if(li == 0 || h[l] > h[li]){
li = l;
}
l--;
}
while(r <= n && h[r] < h[i]){
if(ri == 0 || h[r] > h[ri]){
ri = r;
}
r++;
}
cout << li << ' ' << ri << '\n';
}
}
return 0;
}
优化—单调栈题解：维护一个单调递减的栈。 找每一个数的左使者，从左到右遍历，遍历到当前数h[i]时，把栈顶中小于h[i]的数都出栈并且记录出栈的数中最高的就是当前学生h[i]的左使者。（栈顶中小于h[i]的数是当前数所能挡到的也是它能看到的数） 找每一个数的右使者与左使者相同，方向为从右向左遍历。
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int h[N];
pair<int, int> p[N];//存储 左边使者和右使者
int main()
{
int k;
cin >> k;
for(int ti = 1; ti <= k; ti++){
int n;
cin >> n;
for(int i = 1; i <= n; i++)cin >> h[i];
cout << "Case " << ti << ":\n";
stack<int> q; //维护从大到小（存下标）
//左边
for(int i = 1; i <= n; i++){
if(i == 1){//第一个数没有左使者 = 0
p[i].first = 0;
q.push(i);
}else{
int pre = -1;//记录最大的
while(q.size() && h[q.top()] <= h[i]){//栈顶 <= h[i]的都要出栈
if(h[q.top()] < h[i])pre = q.top();//更新比 h[i]矮的最大值
q.pop();//出栈
}
if(pre == -1)p[i].first = 0; //没有最大值
else{
p[i].first = pre;
}
q.push(i);
}
}
//右边
q = stack<int>{};
for(int i = n; i > 0; i--){
if(i == n){
p[i].second = 0;
q.push(i);
}else{
int pre = -1;
while(q.size() && h[q.top()] <= h[i]){
if(h[q.top()] < h[i])pre = q.top();
q.pop();
}
if(pre == -1)p[i].second = 0;
else{
p[i].second = pre;
}
q.push(i);
}
}
for(int i = 1; i <= n; i++){
cout << p[i].first << ' ' << p[i].second << "\n";
}
}
return 0;
}