*A.黑白边 *
为了让白边使用次数最小，可以先连全部的黑边再连白边。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long read()
{
long long x = 0; bool s = 0; char ch = 0;
while (!isdigit(ch)) { s |= (ch == '-'); ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch - 48); ch = getchar(); }
return s ? -x : x;
}
struct node{
int x,y,flag;
};
vector<node>g;
vector<node>v;
int vis[300000];
int tp(int s)
{
if(s==vis[s])
return s;
return vis[s]=tp(vis[s]);
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
vis[i]=i;
for(int i=1;i<=m;i++)
{
int q,w,e;
cin>>q>>w>>e;
if(e==0)
g.push_back({q,w,e});
else
v.push_back({q,w,e});
}
for(node k:g)
{
if(tp(k.x)!=tp(k.y))
vis[tp(k.x)]=tp(k.y);
}
int ans=0;
for(node k:v)
{
if(tp(k.x)!=tp(k.y))
{
vis[tp(k.x)]=tp(k.y);
ans++;
}
}
set<int>p;
for(int i=1;i<=n;i++)
{
p.insert(tp(i));
}
if(p.size()==1)
cout<<ans;
else
{
cout<<-1;
}
getchar();
getchar();
}*B.最好的宝石 *
区间操作使用线段树，每个节点维护最大值和最大值的个数，对于区间合并分情况讨论，如果是两区间最大值相等，最大值个数就要相加，否则就是较大一方的最大值了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long read()
{
long long x = 0;
bool s = 0;
char ch = 0;
while (!isdigit(ch))
{
s |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch - 48);
ch = getchar();
}
return s ? -x : x;
}
int a[600000];
struct node
{
int l, r, mx, sum;
} g[800000];
typedef pair<int, int> p;
void build(int q, int x, int y)
{
g[q].l = x;
g[q].r = y;
if (x == y)
{
g[q].mx = a[x];
g[q].sum = 1;
return;
}
int mid = x + y >> 1;
build(q * 2, x, mid);
build(q * 2 + 1, mid + 1, y);
if (g[q * 2].mx == g[q * 2 + 1].mx)
{
g[q].mx = g[q * 2].mx;
g[q].sum = g[q * 2].sum + g[q * 2 + 1].sum;
}
else if (g[q * 2].mx > g[q * 2 + 1].mx)
{
g[q].mx = g[q * 2].mx;
g[q].sum = g[q * 2].sum;
}
else
{
g[q].mx = g[q * 2 + 1].mx;
g[q].sum = g[q * 2 + 1].sum;
}
}
p query(int q, int x, int y)
{
p mx = make_pair(0, 0);
if (x <= g[q].l && y >= g[q].r)
{
p k = make_pair(g[q].mx, g[q].sum);
return k;
}
int mid = g[q].l + g[q].r >> 1;
if (x <= mid)
{
p t1 = query(q * 2, x, y);
if (t1.first > mx.first)
{
mx = t1;
}
else if (t1.first == mx.first)
{
mx.second += t1.second;
}
}
if (y > mid)
{
p t2 = query(q * 2 + 1, x, y);
if (t2.first > mx.first)
{
mx = t2;
}
else if (t2.first == mx.first)
{
mx.second += t2.second;
}
}
return mx;
}
void change(int q, int x, int y)
{
if (g[q].l == g[q].r && g[q].l == x)
{
g[q].mx = y;
return;
}
int mid = g[q].l + g[q].r >> 1;
if (x <= mid)
{
change(q * 2, x, y);
}
else
{
change(q * 2 + 1, x, y);
}
if (g[q * 2].mx == g[q * 2 + 1].mx)
{
g[q].mx = g[q * 2].mx;
g[q].sum = g[q * 2].sum + g[q * 2 + 1].sum;
}
else if (g[q * 2].mx > g[q * 2 + 1].mx)
{
g[q].mx = g[q * 2].mx;
g[q].sum = g[q * 2].sum;
}
else
{
g[q].mx = g[q * 2 + 1].mx;
g[q].sum = g[q * 2 + 1].sum;
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
build(1, 1, n);
for (int i = 1; i <= m; i++)
{
string s;
int d, f;
cin >> s >> d >> f;
if (s == "Ask")
{
p k = query(1, d, f);
cout << k.first << " " << k.second << "\n";
}
else
{
change(1, d, f);
}
}
getchar();
getchar();
}C.滑板上楼梯
每次跳4格，3，1轮流跳
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long read()
{
long long x = 0; bool s = 0; char ch = 0;
while (!isdigit(ch)) { s |= (ch == '-'); ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch - 48); ch = getchar(); }
return s ? -x : x;
}
int main()
{
ll n;
cin>>n;
ll k=n%4;
ll ans=n/4;
if(k==3)
cout<<ans*2+1;
else
cout<<ans*2+k;
getchar();
getchar();
}*D.GCD *
把1-n的素数筛出来，结果为素数种类+1.时间复杂度n
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long read()
{
long long x = 0;
bool s = 0;
char ch = 0;
while (!isdigit(ch))
{
s |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch - 48);
ch = getchar();
}
return s ? -x : x;
}
int a[500000];
int main()
{
int n;
cin >> n;
for (int i = 2; i <= n; i++)
{
int k = i;
for (int j = 2; j <= sqrt(i); j++)
{
if (k % j == 0)
{
while (k % j == 0)
k /= j;
a[j]++;
}
}
if (k > 1)
{
a[k]++;
}
}
int mx = 0;
int flag=0;
for (int i = 2; i <= n; i++)
{
if(a[i])
{
mx++;
if(a[i]>=2)
flag=1;
}
}
if(flag)
cout<<mx+2;
else
{
cout<<-1;
}
getchar();
getchar();
}*E.牛牛的加法 *
模拟，主要前导零
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long read()
{
long long x = 0;
bool s = 0;
char ch = 0;
while (!isdigit(ch))
{
s |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch - 48);
ch = getchar();
}
return s ? -x : x;
}
string add(string a, string b)
{
string s = "";
int l = a.length() - 1;
int r = b.length() - 1;
while (l >= 0 && r >= 0)
{
int aa = a[l] - '0';
int bb = b[r] - '0';
aa = (aa + bb) % 10;
s = (char)(aa + '0') + s;
l--;
r--;
}
while (l >= 0)
{
s = a[l] + s;
l--;
}
while (r >= 0)
{
s = b[r] + s;
r--;
}
return s;
}
int main()
{
string a, b;
cin >> a >> b;
string k = add(a, b);
while (k.length())
{
if (k[0] == '0')
k.erase(0,1);
else
{
break;
}
}
if (k.length() == 0)
cout << 0;
else
{
cout << k;
}
getchar();
getchar();
}*F.石子合并 *
贪心，每次拿最大值和别人合并
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long read()
{
long long x = 0; bool s = 0; char ch = 0;
while (!isdigit(ch)) { s |= (ch == '-'); ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch - 48); ch = getchar(); }
return s ? -x : x;
}
int a[400000];
int main()
{
int n;
cin>>n;
int mx=0;
int index=0;
ll sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>mx)
{
mx=a[i];
index=i;
}
}
for(int i=1;i<=n;i++)
{
if(i!=index)
sum+=(mx+a[i]);
}
cout<<sum;
getchar();
getchar();
}G.滑板比赛
应该是双指针，这里用了二分。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long read()
{
long long x = 0;
bool s = 0;
char ch = 0;
while (!isdigit(ch))
{
s |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch - 48);
ch = getchar();
}
return s ? -x : x;
}
vector<int> g;
int b[400000];
int main()
{
int n, m;
cin >> n >> m;
int ans = 0;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
g.push_back(x);
}
for (int i = 1; i <= m; i++)
cin >> b[i];
sort(g.begin(), g.end());
for (int i = 1; i <= m; i++)
{
int k = upper_bound(g.begin(), g.end(), b[i]) - g.begin();
if (k < g.size())
{
ans++;
g.erase(g.begin() + k);
}
}
cout << ans;
getchar();
getchar();
}*H.第 k 小 *
用最大堆维护前k小，后面没有就舍弃了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long read()
{
long long x = 0;
bool s = 0;
char ch = 0;
while (!isdigit(ch))
{
s |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch - 48);
ch = getchar();
}
return s ? -x : x;
}
priority_queue<int> p;
int main()
{
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
int w;
cin >> w;
p.push(w);
if (p.size() > k)
p.pop();
}
for (int i = 1; i <= m; i++)
{
int w;
cin >> w;
if (w == 1)
{
int e;
cin >> e;
p.push(e);
if (p.size() > k)
p.pop();
}
else
{
if(p.size()==k)
cout << p.top() << "\n";
else
{
cout<<"-1"<<"\n";
}
}
}
getchar();
getchar();
}*I.区间异或 *
时间复杂度On（nn+nm）发现暴力也能过。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[600000];
int dp[5000][5000];
int p[600000];
vector<int> g;
map<ll, int> vis;
inline long long read()
{
long long x = 0;
bool s = 0;
char ch = 0;
while (!isdigit(ch))
{
s |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch - 48);
ch = getchar();
}
return s ? -x : x;
}
int main()
{
ll n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
a[i]=read();
}
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
dp[i][j] = dp[i][j - 1] xor a[j];
p[j-i+1] = max(p[j-i+1], dp[i][j]);
}
}
sort(g.begin(), g.end());
for (int i = 1; i <= m; i++)
{
int w;
w=read();
int flag=1;
for(int j=1;j<=n;j++)
{
if(p[j]>=w)
{
flag=0;
cout<<j<<"\n";
break;
}
}
if(flag)
cout<<"-1"<<"\n";
}
getchar();
getchar();
}J.小游戏
dp
dp[i]=max(dp[i],max(dp[i-1],dp[i-2]+cnt[i]*i))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long read()
{
long long x = 0;
bool s = 0;
char ch = 0;
while (!isdigit(ch))
{
s |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch - 48);
ch = getchar();
}
return s ? -x : x;
}
vector<ll> p;
ll cnt[300000];
ll v[300000];
ll dp[300000];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
ll w;
cin>>w;
cnt[w]++;
if (!v[w])
{
v[w] = 1;
p.push_back(w);
}
}
sort(p.begin(), p.end());
ll mx = 0;
for (int i = 1; i <= 2e5; i++)
{
if (i == 1)
{
dp[i] = cnt[i];
continue;
}
dp[i] = max(dp[i], max(dp[i - 1], dp[i - 2] + cnt[i] * i));
mx = max(mx, dp[i]);
}
cout << mx;
getchar();
getchar();
}
京公网安备 11010502036488号