Java教程

700题复习计划

本文主要是介绍700题复习计划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

review

AT193

将n个数从小到大排序,挨个输出

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
string a[105];
int n,m;
bool cmp(string x,string y){
    return x+y>y+x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        cout<<a[i];
    }
    cout<<"\n";
    return 0;
}

CF898D

将闹钟响的时间排序,枚举 \(i\),如果 \(a_i\) 到 \(a_i + m\) 这个区间内有大于k 个闹钟的话,就贪心将后面的删去,直到这个区间内只有 k 个为止

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

const int N = 2e5 + 10, M = 1e6 + 10;

int n, m, k;
int a[N], cnt;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    
    deque<int> dq;
    
    for (int i = 1; i <= n; ++i)
    {
        while (dq.size() && dq.front() <= a[i] - m)
            dq.pop_front();
        dq.push_back(a[i]);
        while (dq.size() >= k)
            ++cnt, dq.pop_back();
    }
    cout << cnt << endl;
    return 0;
}
//

CF898C

将每一个人的号码排序,判断是否存在后缀的情况,有就删,没有就保留

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 25;

map<string,vector<string> >mp;
bool cmp(string s1,string s2)
{
    return s1<s2;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    string name,ss;
    for(int i=1; i<=n; i++)
    {
        cin>>name;
        int m;
        cin>>m;
        while(m--)
        {
            cin>>ss;
            reverse(ss.begin(),ss.end());//先翻转存入便于判断后缀
            mp[name].push_back(ss);
        }
    }
    cout<<mp.size()<<endl;
    map<string,vector<string> >::iterator it;
    for(it=mp.begin(); it!=mp.end(); it++)
    {
        string str[1000],ans[1000];
        cout<<it->first<<" ";
        vector<string>v=it->second;
        int len=v.size();
        for(int i=0; i<len; i++)
        {
            str[i]=v[i];
        }
        sort(str,str+len,cmp);
        int i,j,k=0;
        for(i=0; i<len; i++)
        {
            int temp,flag=0;
            for(j=i+1; j<len; j++)
            {
                temp=str[j].find(str[i]);
                if(temp==0)
                {
                    flag=1;
                    break;
                }
            }
            if(flag==0)
            {
                ans[++k]=str[i];
            }
        }
        cout<<k;
        for(int i=1; i<=k; i++)
        {
            reverse(ans[i].begin(),ans[i].end());
            cout<<" "<<ans[i];
        }
        cout<<endl;
    }
}
//

CF898B

枚举 \(x\) ,二分 \((n - a \times x) \mod b\) 是否等于 0

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 0;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n,a,b;
    cin>>n>>a>>b;

    for(int i=0;i<=n/a;i++)
        if((n - i * a) % b == 0)
        {
            cout<<"YES"<<endl;
            cout<<i<<' '<<(n - a * i) / b;
            return 0;
        }

    cout<<"NO";

    return 0;
}
//

CF877E

用\(dfs\)序来找到子树,一个子树作为一段来建线段树

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
struct Tree
{
	int l,r;
	int turn;
	int sum;
	int mid;
} tr[N * 4];

vector<int> g[N];//存图

int in[N],out[N],order[N],times = 0;// 进入栈的时间,出栈的时间,dfs序,当前时间
void dfs(int root,int father)
{
	in[root] = ++times;
	order[times] = root;

	int len = g[root].size();
	for(int i=0; i<len; i++)
	{
		int v = g[root][i];
		if(v == father) continue;
		dfs(v,root);
	}

	out[root] = times;
}

void pushup(int u)
{
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
	if(tr[u].turn)
	{
		tr[u<<1].turn ^= 1, tr[u<<1|1].turn ^= 1;
		tr[u<<1].sum = tr[u<<1].r - tr[u<<1].l + 1 - tr[u<<1].sum;// xor
		tr[u<<1|1].sum = tr[u<<1|1].r - tr[u<<1|1].l + 1 - tr[u<<1|1].sum;// xor
		tr[u].turn = 0;
	}
}

int w[N];//原开关情况
void build(int u,int l,int r)
{
	if(l == r) tr[u].l = l,tr[u].r = r,tr[u].turn = 0,tr[u].sum = w[order[l]];
	else
	{
		tr[u].l = l,tr[u].r = r,tr[u].turn = 0;
		int mid = l + r >> 1;
		tr[u].mid = mid;

		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

void modify(int u,int l,int r)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].sum = tr[u].r - tr[u].l + 1 - tr[u].sum; // xor
		tr[u].turn ^= 1;
	}
	else
	{
		pushdown(u);
		if(l <= tr[u].mid) modify(u<<1,l,r);
		if(r > tr[u].mid) modify(u<<1|1,l,r);
		pushup(u);
	}
}

int query(int u,int l,int r)
{
	if(tr[u].r < l || tr[u].l > r) return 0;
	if(tr[u].l >= l && r >= tr[u].r) return tr[u].sum;

	pushdown(u);
	int res = 0;

	if(l <= tr[u].mid) res += query(u<<1,l,r);
	if(r > tr[u].mid) res += query(u<<1|1,l,r);

	pushup(u);

	return res;
}

int main()
{
	int n;
	cin>>n;
	for(int i=2; i<=n; i++)
	{
		int x;
		scanf("%d",&x);
		g[x].push_back(i);
		g[i].push_back(x);
	}
	for(int i=1; i<=n; i++) scanf("%d",&w[i]);

	dfs(1,-1);
	build(1,1,n);

	int q;
	scanf("%d",&q);
	while(q--)
	{
		char opt[4];
		int x;
		scanf("%s%d",opt,&x);

		if(opt[0] == 'p') modify(1,in[x],out[x]);
		else cout << query(1,in[x],out[x]) << endl;
	}

	return 0;
}
//

CF787B

如果一个团队中没有出现绝对值相同的两个数,就是YES,否则NO

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 1e4+10;

unordered_map<int,int> t;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	int n,m;
	cin>>n>>m;

	for(int i=1;i<=m;i++)
	{
		int k;
		cin>>k;

		t.clear();

		bool flag = 0;
		for(int i=1;i<=k;i++)
		{
			int x;
			cin>>x;
			t[x] = 1;
			if(t[-x])
			{
				flag = 1;
			}
		}
		if(!flag) 
		{
			cout<<"YES";
			return 0;
		}
	}

	cout<<"NO";

    return 0;
}
//

CF776B

质数为1,否则为2

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

bool st[N];
int prime[N],cnt=0;

void gets_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j=0;prime[j] <= n/i;j++)
        {
            st[prime[j] * i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
    
    return ;
}
int main()
{
	int n;
	cin>>n;
	
	gets_prime(n+2); 
	
	if(n < 3) cout<<1<<endl;
	else cout<<2<<endl;
 
 
 	for(int i=2;i<=n+1;i++)
 	{
 		if(st[i]) cout<<2<<' ';
 		else cout<<1<<' ';
	}
	
	return 0;
} 

CF734C

考虑不用药,\(ans = n * w\)

考虑只用第一种药,如果\(b[i]\le s\),就更新答案 \(ans = min(ans,n * a[i])\)

考虑只用第二种药,如果\(d[i]\le s\),就更新答案 \(ans = min(ans,(n-c[i]))\)

考虑先用第一种药,再在d中二分出 \(x\) 为 \(s - b[i]\) 的位置, \(ans = min(ans, (n-c[x]) * a[i]\)

#include <bits/stdc++.h>
using namespace std;

const int INF= 0x3f3f3f3f;
const int N=2e5+5;
typedef long long LL;

LL n,m,k,w,s;
LL b[N],c[N];

struct Node
{
	LL x;
	LL y;
} a[N];

int main()
{
	scanf("%d%d%d%d%d",&n,&m,&k,&w,&s);
	for(int i=1; i<=m; i++) scanf("%d",&a[i].x);
	for(int i=1; i<=m; i++) scanf("%d",&a[i].y);
	for(int i=1; i<=k; i++) scanf("%d",&b[i]);
	for(int i=1; i<=k; i++) scanf("%d",&c[i]);

	LL time=n*w;
	for(int i=1; i<=k; i++)
	{
		if(c[i] <= s)
		{
			time=min(time, (n-b[i])*w );
		}
	}
	for(int i=1; i<=m; i++)
	{
		if(a[i].y <= s)
		{
			time=min(time, n*a[i].x );
		}
	}
	for(int i=1; i<=m; i++)
	{
		if(a[i].y > s) continue;

		LL aa=upper_bound(c+1,c+1+k, s-a[i].y )-(c+1);
		if(c[aa] <= s-a[i].y)
			time=min(time, (n-b[aa])*a[i].x) ;
	}
	
	cout<<time;

	return 0;
}

CF898A

将一个数四舍五入。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 0;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    int a = n % 10;
    int b = 10 - (n % 10);

    if(a < b) cout<<n - a;
    else cout<< n + b;

    return 0;
}
//

CF811A

模拟,实在没啥可以解释的

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a,b;
    cin>>a>>b;
    
    int k = 1;
    while(1)
    {
        if(a < k) 
        {
            cout<<"Vladik"<<endl;
            break;
        }
        a -= k;
        k++;
        if(b < k)
        {
            cout<<"Valera"<<endl;
            break;
        }
        b -= k;
        k ++;
    }

    return 0;
}

CF808A

所有的lucky year都可以表示为 \(j * 10^i\) ,枚举 \(i\) 和 \(j\) 即可。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    for(int i=1;;i*=10)
    {
        bool flag = 0;
        for(int j=1;j<=9;j++)
        {
            if(i * j > n)
            {
                cout<<i*j-n<<endl;
                flag = 1;
                break;
            }
        }
    
        if(flag) break;
    }
    
    return 0;
}

CF787A

枚举时刻 \(i\), 当 \((i - b) \mod a == 0 \; and \;(i - d) \mod c == 0\) 即输出i

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 0;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	int a,b,c,d;
	cin>>a>>b>>c>>d;

	for(int i=0;i<=100000000;i++)
	{
		if(i-b >= 0 && i-d >= 0 && (i - b) % a == 0 && (i - d) % c == 0) 
		{
			cout<<i;
			return 0;
		}
	}

	cout<<-1;

    return 0;
}
//

CF786A

现在我们知道 1 是必败态,那么我们通过 \(DFS\) 可以判断每个点的胜负情况、是否有解。

我们考虑逆向思维,对每个玩家在 1 时的先手状态向前转移,具体过程如下:

  1. 定义 \(DFS(v,now)\) 表示现在是 \(now\)的位置,玩家 \(v\) 先手。
  2. 枚举上一次玩家 \(u\) 的操作 \(x\),那么可以从 \(now-x\) 的位置转移到 \(now\) 的位置(注意这里的 \(now-x\) 不能等于 \(1\))。
  3. 如果 \(now\) 的位置是必败态,那么根据结论:能转移到必败态的状态就是必胜态,可以得到 \(now-x\) 的位置是必胜态。
  4. 如果 \(now\) 的位置是必胜态,那么根据结论:只能转移到必胜态的状态就是必败态。我们记 \(cnt_{u,i}\) , \(i\) 表示在\(i\) 这个位置且 u 先手可以转移到的必胜态数量。当 \(cnt_{u,now-x}+1=k_u\),时,意味着从 \((u,now-x)\) 转移到的所有状态都是必胜态,那么意味着从 \((u,now-x)\) 这个状态为必败态。
  5. 继续 \(DFS(u,now-x)\) 进行转移即可。
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 7005;

int k[2];
int cnt[2][N];
int step[2][N];
bool vis[2][N],win[2][N];
int n;

void dfs(int user,int pos)
{
	if(vis[user][pos]) return ;
	vis[user][pos] = 1;
	int u = user ^ 1;

	for(int i=1;i<=k[u];i++)
	{
		int pre = (pos - step[u][i] + n - 1) % n + 1;

		if(pre == 1) continue;
		if(!win[user][pos])
		{
			win[u][pre] = 1;
			dfs(u,pre);
		}
		else if(++cnt[u][pre] == k[u])
		{
			win[u][pre] = 0;
			dfs(u,pre);
		}
	}
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin>>n;
	for(int i=0;i<=1;i++)
	{
		cin>>k[i];
		for(int j=1;j<=k[i];j++)
			cin>>step[i][j];
	}


	dfs(0,1);
	dfs(1,1);

	for(int i=0;i<=1;i++) 
	{
		for(int j=2;j<=n;j++)
		{
			if(!vis[i][j]) cout<<"Loop ";
			else if(win[i][j]) cout<<"Win ";
			else cout<<"Lose ";
		}
		cout<<endl;
	}

    return 0;
}
//

CF701B

可以将车平移到四周,类似数学中的一块草地,要在上面铺路,求草地面积。

开个col,row数组记录这一列,行有没有被攻击。

如果新增的车的那一列,行没有攻击过,则n--,或m--

最后输出n * m

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

bool row[N];
bool col[N];

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	
	long long num_row = n,num_col = n;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(!row[x]) row[x] = 1,num_row --;
		if(!col[y]) col[y] = 1,num_col --;
		
		cout<<num_row*num_col<<endl;
	}
	
	return 0;
}
//

CF701A

排序,a[i] 和 a[n - i + 1] 为一对

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

struct Node
{
	int val;
	int id;
	
	bool operator < (const Node& x) const
	{
		return val < x.val;
	}
}a[N];

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].val,a[i].id=i;
	
	sort(a+1,a+1+n);
	
	for(int i=1;i<=n/2;i++)
		cout<<a[i].id<<' '<<a[n-i+1].id<<endl;
	
	return 0;
}

CF664A

如果 a==b ,则为a,否则为1

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string a,b;
    cin>>a>>b;
    
    if(a==b) cout<<a;
    else cout<<1;
    
    return 0;
}

CF608B

处理出 b 的前缀和

如果a[i] == 1,就和b[i.i + n - 1],ans 加上b中以i为左端点,长度为m的区间内0的个数

反之亦然

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 200005;
char a[N],b[N];
int sum[N];

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>a+1>>b+1;

    int n = strlen(a + 1), m = strlen(b + 1);
    for(int i=1;i<=m;i++) sum[i] = sum[i-1] + (b[i] == '0');

    LL ans = 0;
    for(int i=1;i<=n;i++) 
    {
        if(a[i] == '1') ans += sum[m - (n - i)] - sum[i - 1];
        else ans += m - n + i  - sum[m - (n - i)] - i + 1 + sum[i-1]; 
    }

    cout<<ans;

    return 0;
}

CF608A

记录从第i楼出发的乘客的到达时间的最大值

从上到下枚举楼层,如果当前这一层楼的所有乘客都到了。就直接下楼 —— ans++

否则就等到乘客到了位置,再下楼——ans = max(ans,f[i]) + 1

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 1005;

int n,s,x;
int f[N],t[N];

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>x>>t[i],f[x] = max(f[x],t[i]);

    int ans = 0;
    for(int i=s;i>=1;i--)
    {
        ans = max(ans,f[i]);
        ans ++;
    }

    cout<<ans;

    return 0;
}
//

CF606B

阅读题

按照给出的序列走,问第k次走到的点在之前是否走过,并问最后的时候有多少个点没有走过

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 5005;

int n,m;
int x,y;
string s;
bool st[N][N];

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n>>m>>x>>y;
    cin>>s;
    
    int len = s.size(), cnt = 1;
    st[x][y] = 1;
    cout<<1<<' ';
    for(int i=0;i<len-1;i++)
    {
        if(s[i] == 'U' && x > 1) x--;
        if(s[i] == 'D' && x < n) x ++;
        if(s[i] == 'L' && y > 1) y --;
        if(s[i] == 'R' && y < m) y ++;

        if(!st[x][y]) cout<<1<<' ',cnt++;
        else cout<<0<<' ';
        st[x][y] = 1;
    }

    cout << n * m - cnt;

    return 0;
}
//

CF606A

每两个同色剩余可以换一个欠的

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 0;

int a[5],b[5],c[5];

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n = 3;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    int add = 0,sub = 0;
    for(int i=1;i<=n;i++) c[i] = a[i] - b[i];
    for(int i=1;i<=n;i++) 
    {
        if(c[i] < 0) sub += c[i];
        if(c[i] > 0) add += c[i] / 2;
    }

    // cout<<add<<' '<<sub<<endl;

    if(add + sub >= 0) cout<<"Yes";
    else cout<<"No";

    return 0;
}
//

CF554B

如果这两行是一样的,整列翻转只有长的也一样

#include <bits/stdc++.h>
using namespace std;

unordered_map<string,int> h;
string s;

int main()
{
    int n;
    cin>>n;
    
    for(int i=1;i<=n;i++) cin>>s,h[s]++;
    
    int res = 0;
    for(auto x : h) 
        res = max(res,x.second);
        
    cout<<res;
    
    return 0;
}

CF456B

\((1^n + 2^n + 3^n + 4^n) \mod 5 = (1^n \mod 5 + 2^n \mod 5 + 3^n \mod 5 + 4^n \mod 5) \mod 5\)

根据费马小定理:\(a^{5-1} \equiv 1 (mod \;5)\)

所以原式 $ = (1^{n; mod;4} + 2^{n; mod;4} + 3^{n; mod;4} + 4^{n; mod;4}) \mod 5$

最后打个高精模吗,搞定

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 0;


int mod(string a,int b)//高精度a除以单精度b
{
    int d=0;
    for(int i=0;i<a.size();i++)  d=(d*10+(a[i]-'0'))%b;  //求出余数
    return d;
}

int power(int x,int y)
{
    int ans = 1;
    for(int i=1;i<=y;i++) ans *= x;
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	string n;
    cin>>n;

    int mi = mod(n,4);

    LL ans = (power(2,mi) % 5 + power(3,mi) % 5 + power(4,mi) + 1) % 5;

    cout<<ans;

    return 0;
}
//

CF456A

按价格排序,维护质量前缀最大值,发现前缀最大值比 \(b_i\) 大,就Happy,反之亦然

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

const int N = 1e5;

PII a[N];
int n;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;

    sort(a+1,a+1+n);

    for(int i=1;i<n;i++)
    {
        if(a[i].first < a[i+1].first && a[i].second > a[i+1].second)
        {
            cout<<"Happy Alex";
            return 0;
        }
    }

    cout<<"Poor Alex";

    return 0;
} 
//
这篇关于700题复习计划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!