签到
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
string s;
while(n){
s+=n%10+'0';
n/=10;
}
cout<<s<<endl;
return 0;
}
可以桶排
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+5;
int a[maxn];
int main(){
int n,k,max=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>k;
a[k]++;
}
for(int i=1;i<=30000;i++)
if(a[i]>max)
max=a[i];
for(int i=1;i<=30000;i++)
if(a[i]==max)
cout<<i<<" "<<a[i]<<endl;
return 0;
}
注意开 long long
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main() {
ll a[105]={0,0,1};
int n;
scanf("%d",&n);
for(int i=3;i<=n;i++)
a[i]=a[i-1]+a[i-2];
printf("%lld",a[n]);
return 0;
}
法一:
#include<iostream>
#include<map>
using namespace std;
int main(){
int n;
map<int,int> a;
cin>>n;
int t;
for(int i=0;i<n;i++){
cin>>t;
a[t]++;
}
for(map<int,int>::iterator i=a.begin();i!=a.end();i++)
if((i->second)%2==1){
cout<<i->first<<endl;
break;
}
}
法二:
#include<bits/stdc++.h>
using namespace std;
int main(){
int ans,n;
cin>>n>>ans;
for(int i=2;i<=n;i++){
int t;
cin>>t;
ans=ans^t;
}
cout<<ans;
return 0;
}
法一:
一天一天模拟即可,$O(n)$
#include<iostream>
using namespace std;
long long ans,n;
int cnt=1;
int main(){
cin>>n;
int j=0;
for(int i=1;i<=n;i++){
ans+=cnt;
j++;
if(j==cnt) cnt++,j=0;
}
cout << ans << endl;
}
法二:
卡时间时,这是通解,$O(\sqrt{n})$,当然可以二分找 $t$,那么就 $O(log{n})$了
推公式,先找到一个 $t$ 满足$\dfrac{\left( 1+t\right) *t}{2}\leq n< \dfrac{\left( t+1\right) * (t+2)}{2}$,然后求$\left( 1+t\right) \left( n-\dfrac{\left( 1+t\right) t}{2}\right)+\sum ^{t}_{i=1}i^{2}$即可
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
int n;
cin >> n;
int d;
for(int i=0;i<=sqrt(2*n)+1;i++){
if(i*(i+1)/2>n){
d=i;break;
}
}
d--;
ll sum=0;
sum+=(1+d)*(n-d*(d+1)/2);
for(int i=1;i<=d;i++)
sum+=i*i;
cout<<sum<<endl;
}
本题不能暴力去做,题解是薛同写的,在此放上
解释:
题意不太清楚,在此道歉,开心数应该是它的二进制数位上有且仅有一位是为0的
思路:
找出所有在二进制表示的情况下,所有位数都为1的数。然后拿这些数分别减2的次幂(其指数比该数的最高位数低)的所有情况,一 一列举
例如:
11 10
111 110 101
1111 1110 1101 1011
先将上述的枚举数存到数组,再根据给的范围得出所喜欢的数的个数
#include<iostream>
using namespace std;
typedef long long ll;
ll n[61] = { 1 };
ll m[2000] = { 0 };
int cnt = 1;
void init(){
//n存储2的0-60次幂,因为10^18的二进制位位数为60
for (int i = 1; i < 61; i++)
n[i] = n[i-1] * 2;
//选择一个1挖掉,m存储二进制仅含一个零的数(m数组一定严格递增)
for (int i = 2; i < 61; i++)
for (int j = i - 2; j >= 0; j--)
m[cnt++] = n[i] -1 - n[j] ;//枚举喜欢的数
}
int main() {
init();
int t;
cin >> t;
while (t--) {
ll l, r;
cin >> l >> r;
int pos = 0;
while (m[pos] < l) pos++;
int count = 0;
for (; pos <= cnt; pos++) {
if (m[pos] > r)
break;
count++;
}
cout << count << endl;
}
}
思路:
暴力打表判断就好(不打表也能过),好多人wa在了0的判断,0!=1,那么0不能表示成为一些互不相同的整数的阶乘之和,所以输出NO就好了
枚举代码:
#include<iostream>
using namespace std;
int n;
int m[10] = { 1 };
int main() {
for (int i = 1; i < 10; i++)
m[i] = m[i - 1] * i;
while (cin >> n && n >= 0) {
if (n != 0) {
for (int i = 9; i >= 0; i--) {
if (n >= m[i])
n = n - m[i];
if (n == 0) {
cout << "YES" << endl;
break;
}
}
if (n)
cout << "NO" << endl;
}
else
cout<<"NO"<<endl;
}
}
dfs代码:
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=100003;
ll a[13];
bool st[1000010];
//现在的开心数,阶乘所在位置
void dfs(int x, int p){
if(p==-1) return;
st[x+ a[p]]=1;
dfs(x, p - 1);//不加
dfs(x + a[p], p - 1);//加
}
int main(){
a[0]=a[1]=1;
for(int i=2;i<10;i++) {
a[i]=a[i-1]*i;
}
dfs(0, 9);
int x;
while(scanf("%d",&x),x>=0){
if(st[x]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
思路:
简单bfs,3X3的块间没有干扰,所以queue也不需要,枚举就可以
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
char mp[103][103];
int dir[][2] = {1, 0, 0, 1, 1, -1, -1, 1, -1, 0, 0, -1, -1, -1, 1, 1};
int main() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; ++i) {
cin >> (mp[i + 1] + 1);
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(mp[i][j] == '*') {
cout << "*";
continue;
}
int cnt = 0;
for(int k = 0; k < 8; ++k) {
int x = i + dir[k][0];
int y = j + dir[k][1];
if(mp[x][y] == '*') cnt++;
}
cout << cnt;
}
cout << endl;
}
return 0;
}
思路:
并查集,如果2个人是朋友,就union起来,如果是敌人,就把自己和对方的朋友union起来,中间标记一下自己的敌人就好
#include<iostream>
using namespace std;
int p[1005];
int d[1005];
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
void un(int x, int y) {
int a = find(x);
int b = find(y);
if (a != b) p[b] = a;
}
int main() {
int n, m;
int v, x, y;
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 0; i < m; i++) {
cin >> v >> x >> y;
if (!v){
un(x, y);//连接队友
}
else {//x和y是敌人
if (d[x])
un(y, d[x]);//x的敌人是y的朋友,连接2个集合
if (d[y])
un(x, d[y]);//y的敌人是x的朋友,连接2个集合
//标记敌人
d[x] = y;
d[y] = x;
}
}
int s = 0;
for (int i = 1; i <= n; i++)
if (p[i] == i)
s++;
cout << s;
}
题目全半角搞混了,在此道歉QAQ
思路:
栈的基本应用,用数组模拟或者写一个栈就好
数组:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char c[300];
int cnt;
int main(){
string s;
cin>>s;
int len=s.size();
for(int i=0;i<len;i++){
if(cnt!=0 && (s[i]==')'&&c[cnt]=='(' || s[i]==']'&&c[cnt]=='[')) cnt--;
else c[++cnt]=s[i];
}
if(cnt==0) cout<<"happy"<<endl;
else cout<<"unhappy"<<endl;
}
STL(这里直接find函数了):
#include<iostream>
using namespace std;
int cnt;
int main(){
string s;
cin>>s;
string::iterator it=s.begin();
while(1){
int pos=0;
if(s.find("()")!=-1){
pos=s.find("()");
s.erase(it+pos,it+pos+2);
}
else if(s.find("[]")!=-1){
pos=s.find("[]");
s.erase(it+pos,it+pos+2);
}
else break;
}
if(s.size()==0) cout<<"happy"<<endl;
else cout<<"unhappy"<<endl;
}
思路:
一道简单数学题,正向考虑卖不出去的个数有点难搞,那就逆向,考虑能卖出去的情况数,1号小圆球可以有M个情况,2号小圆球就有(M-1)个情况,3号小圆球也是(M-1)个情况,以此类推得到能卖出去的情况数为:$M*(M-1)^{(N-1)} $,总方案数为:$M^N$,注意模数作差即可
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod= 100003;
ll n,m,p;
//快速幂
ll qpow(ll a,ll b){
ll ans = 1;
while(b){
if(b&1) ans = (ans*a)%mod;
b/=2;
a = (a*a)%mod;
}
return ans;
}
int main(){
cin>>m>>n;
printf("%lld\n",(qpow(m,n)-(m*qpow(m-1,n-1))%mod+mod)%mod);
return 0;
}
思路:
abc 3个矩阵的乘积方式有abc,acb,bac,bca,cab,cba 6种
那么枚举这6种的开心值,如果开心值不存在,就是-1
最后如果6种情况都是-1,输出ERROR,反之输出这六个数的最大值
#include<bits/stdc++.h>
#define ll long long
#define fo(i,a,b) for(int i=a;i<b;i++)
using namespace std;
ll a[105][105],b[105][105],c[105][105];
ll d[105][105],e[105][105];
ll happy[10];
const ll mod=1e9+7;
//计算[n,m] * [m,p]的乘积,存于后一个矩阵
void calculate(ll n, ll m, ll p, ll t1[105][105], ll t2[105][105]){
memset(d,0,sizeof d);
int row=0;//记录d矩阵到哪一行了
int col=0;//记录d矩阵到哪一列了
fo(i,0,n)fo(j,0,p){
ll sum=0;
fo(k,0,m){
sum+= 1LL * t1[i][k] * t2[k][j];
}
if(j!=p-1)
d[row][col++]=sum;
else { //要换行了
d[row][col++]=sum;
row++;
col=0;
}
}
}
void calculate2(ll n, ll m, ll p, ll t1[105][105], ll t2[105][105]){
memset(e,0,sizeof e);
int row=0;//记录e矩阵到哪一行了
int col=0;//记录e矩阵到哪一列了
fo(i,0,n)fo(j,0,p){
ll sum=0;
fo(k,0,m){
sum+= 1LL * t1[i][k] * t2[k][j];
}
if(j!=p-1)
e[row][col++]=sum;
else { //要换行了
e[row][col++]=sum;
row++;
col=0;
}
}
}
//计算矩阵开心值
ll calculate3(ll n,ll m,ll t[105][105]){
ll sum=1;
fo(i,0,n)fo(j,0,m){
sum*=t[i][j];
sum%=mod;
}
return sum;
}
int main(){
int n1,m1,n2,m2,n3,m3;
//输入3个矩阵
cin>>n1>>m1;
fo(i,0,n1)fo(j,0,m1)scanf("%lld",&a[i][j]);
cin>>n2>>m2;
fo(i,0,n2)fo(j,0,m2)scanf("%lld",&b[i][j]);
cin>>n3>>m3;
fo(i,0,n3)fo(j,0,m3)scanf("%lld",&c[i][j]);
//求6次开心值
//abc型([n1,m1] * [n2,m2] * [n3,m3])
if(m1==n2&&m2==n3){//存在开心值
calculate(n1,m1,m2,a,b);
calculate2(n1,m2,m3,d,c);
happy[0]=calculate3(n1,m3,e);
}
else happy[0]=-1;
//acb型([n1,m1] * [n3,m3] * [n2,m2])
if(m1==n3&&m3==n2){
calculate(n1,m1,m3,a,c);
calculate2(n1,m3,m2,d,b);
happy[1]=calculate3(n1,m2,e);
}
else happy[1]=-1;
//bac型([n2,m2] * [n1,m1] * [n3,m3])
if(m2==n1&&m1==n3){
calculate(n2,m2,m1,b,a);
calculate2(n2,m1,m3,d,c);
happy[2]=calculate3(n2,m3,e);
}
else happy[2]=-1;
//bca型([n2,m2] * [n3,m3] * [n1,m1])
if(m2==n3&&m3==n1){
calculate(n2,m2,m3,b,c);
calculate2(n2,m3,m1,d,a);
happy[3]=calculate3(n2,m1,e);
}
else happy[3]=-1;
//cab型([n3,m3] * [n1,m1] * [n2,m2])
if(m3==n1&&m1==n2){
calculate(n3,m3,m1,c,a);
calculate2(n3,m1,m2,d,b);
happy[4]=calculate3(n3,m2,e);
}
else happy[4]=-1;
//cba型([n3,m3] * [n2,m2] * [n1,m1])
if(m3==n2&&m2==n1){
calculate(n3,m3,m2,c,b);
calculate2(n3,m2,m1,d,a);
happy[5]=calculate3(n3,m1,e);
}
else happy[5]=-1;
ll mx=-1;
for (int i = 0; i < 6; ++i) {
mx=max(mx,happy[i]);
}
if(mx==-1)cout<<"ERROR";
else cout<<mx;
return 0;
}
思路:
先跑一次spfa看能不能到终点,如果能,那就看距离是不是超过了cnt(这次spfa边权都是1),如果超过了,那就进入正题,我们可以二分最小花费cost,对于如何check,把这张图的边权映射为1或0(大于cost为1,反之为0),再跑spfa就可以了,如果最后终点的最短路小于等于cnt,check就返回true,反之返回false,二分正确是因为解是单调最优的,cost越大就越容易成功,cost越小就越难成功
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int n,m;
int h[N],e[N],w[N],ne[N],idx;
int S,T,num;
int d[N];
bool st[N];
void spfa(){
memset(st,0,sizeof st);
queue<int> q;
q.push(S);
st[S] = 1;
while(q.size()){
int t = q.front();
q.pop();
for(int i = h[t];~i;i = ne[i]){
int j = e[i];
if(st[j]) continue;
st[j] = true;
d[j] = d[t] + 1;//权值设为1
q.push(j);
}
}
}
void add(int x,int y,int z){
ne[idx] = h[x],e[idx] = y,w[idx] = z,h[x] = idx++;
}
bool spfa2(int mid){
memset(st,0,sizeof st);
memset(d,0x3f,sizeof d);
d[S] = 0;
queue<int> q;
q.push(S);
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t];~i;i = ne[i]){
int j = e[i];
int p = w[i] > mid ? 1 : 0;
if(d[j] > d[t] + p){
d[j] = d[t] + p;
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return d[T] <= num;
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m>>S>>T>>num;
while(m--){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z),add(y,x,z);
}
spfa();
if(!st[T]){
puts("No");
return 0;
}
puts("Yes");
if(d[T] <= num){
puts("0");
return 0;
}
int l = 0,r = 1e9;
while(l < r){
int mid = (l + r) >> 1;
if(spfa2(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n",l);
return 0;
}
思路:
贪心的去想,权值越大的越要在最靠边的位置上,那么我们把比较大的值放最右边还是最左边呢,这就需要 $dp$ 了,因此我们就去讨论放在左边多少个,右边多少个,然后状态转移, $f[i][j]$ 表示按从大到小的分配顺序,所有左边分配 $i$ 人,右边分配 $j$ 人的分配方式的最大值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;
cin >> n;
vector<pair<int, int>> a(n);
ll f[n+1][n+1];
memset(f,0,sizeof f);
for (int i = 0; i < n; i++) {
cin >> a[i].first;
a[i].second = i + 1;
}
//按第一维从大到小排序
sort(a.rbegin(), a.rend());
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
int k = i - j;
//放左边
f[j + 1][k] = max(f[j + 1][k], f[j][k] + 1ll * a[i].first * abs(a[i].second - (j + 1)));
//放右边
f[j][k + 1] = max(f[j][k + 1], f[j][k] + 1ll * a[i].first * abs(n - k - a[i].second));
}
}
ll ans = 0;
for (int i = 0; i <= n; i++) ans = max(ans, f[i][n - i]);
cout << ans << '\n';
return 0;
}
Comments
Be the first one to comment on this page!