思路：
三个for判断一下就好了。
但是判断等比数列的时候不能直接除，因为不一定全部整除。
a[2] / a[1] = a[i] / a[i - 1]
a[2] * a[i - 1] = a[i] * a[1]
变成乘法就行了。
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
long long int a[200000];
void solved(){
int n;cin >> n;
for(int i = 1; i <= n; i++)cin >> a[i];
bool f1 = true;
for(int i = 2; i <= n; i++){
if((a[2] - a[1]) != (a[i] - a[i - 1])){
f1 = false;break;
}
}
bool f3 = true;
for(int i = 2; i <= n; i++){
if((a[2] % a[1]) != (a[i] % a[i - 1])){
f3 = false;break;
}
}
bool f2 = true;
for(int i = 2; i <= n; i++){
if(a[2] * a[i - 1] != a[i] * a[1]){
f2 = false;break;
}
}
if(f1 || f2 || f3)cout << "YES" << endl;
else cout << "NO" << endl;
}
int main(){
solved();
return 0;
}
思路：
呜呜呜，这题一开始没看懂跳过去了，最后回过来来看终于看懂了，可惜也没时间了。
每找到一个NowCoder就可以开始计算贡献，会等于它左边的数量乘上右边的数量。
不过一个字符串如果出现两次NowCoder不满足条件，所以我们需要记录一下上一次NowCoder出现的位置。
然后计算贡献即可。
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 10;
char s[maxn];
void solved(){
scanf("%s",s + 1);
int len = strlen(s + 1);
long long int ans = 0;
int last = 0;
for(int i = 1; i <= len; i++){
if(i + 7 <= len && s[i] == 'N' && s[i + 1] == 'o' && s[i + 2] == 'w' && s[i + 3] == 'C'
&& s[i + 4] == 'o' && s[i + 5] == 'd' && s[i + 6] == 'e' && s[i + 7] == 'r'){
ans += (i - last) * (len - (i + 7) + 1);
last = i;
}
}
cout << ans << endl;
}
int main(){
solved();
return 0;
}
思路：
这个题应该是全场最简单的题吧。。。。但是有点细节。。。。而且旋转45度我还是不太熟导致还是没过去，但是思路还是秒了。
因为它是一个菱形，所以我们可以先将这个菱形旋转45度，然后做一个二维前缀和求最大值就行了。
em。。。这题主要就是旋转不太好搞，其它的都还行。
旋转的话，
拿这个旋转为例，可以发现旋转后的菱形是一个n * n + 1,n * n + 1这样的，然后我们可以根据左右对角线我们可以发现原来第(i,j)位置的数字存在旋转后的第(n+i-j,i+(j-1))这个位置。并且我们需要把这个位置标记一下，便于我们枚举所有点的时候确保枚举的点是实实在在存在的点。然后做一个二维前缀和，然后枚举所有点求最大值就好了。
害，，，这种旋转45度的题已经是我第二次做了，我还是没写出来，呜呜呜。。。
代码：
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long int ll;
const int maxn = 5e3 + 10;
int num[maxn][maxn];
ll sum[maxn][maxn];
bool vis[maxn][maxn];
void solved(){
int n,k;cin >> n >> k;k--;
for(int i = 1; i <= n + n - 1; i++)
for(int j = 1; j <= n + n - 1; j++)
num[i][j] = sum[i][j] = 0 ;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &num[n+i-j][i+(j-1)]),vis[n+i-j][i+(j-1)] = 1 ;
for(int i = 1; i <= n + n - 1; i++)
for(int j = 1; j <= n + n - 1; j++)
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + num[i][j];
ll ans = 0;
for(int x = 1; x <= n + n; x ++){
for(int y = 1; y <= n + n; y++){
if(!vis[x][y])continue;
int r2 = min(n + n - 1, x + k), r1 = max(1, x - k) ;
int c2 = min(n + n - 1, y + k), c1 = max(1, y - k) ;
ans = max(ans,sum[r2][c2]-sum[r2][c1-1]-sum[r1-1][c2]+sum[r1-1][c1-1]);
}
}
cout << ans << endl;
}
int main(){
solved();
return 0;
}
思路：
这题写的二分把孩子t傻了，原来正解是并查集(好像也不是很难，为啥孩子要写二分)
为了找到最大的L并且是通路，我们可以把所有路的权值从大到小排序，然后一个一个加到并查集中，一旦s到t是联通的(即父亲节点相同)此时的权值就是最大的L。
当然最大L的路径非常多，我们还需要找最小的R，那么相同的做法，对所有权从小到大排序，然后权小于L的不用考虑，然后一个一个加到并查集中去，一旦s到t联通此时的权就是最小的R。
代码：
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 6e6 + 10;
struct edge{
int u,v,w;
}e[maxn];
bool cmp(edge a,edge b){
return a.w > b.w;
}
bool cmp2(edge a,edge b){
return a.w < b.w;
}
int f[maxn];
int find(int x){
if(x != f[x]){
return f[x] = find(f[x]);
}
return f[x];
}
void solved(){
int n,m,s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
int tot = 0;
for(int i = 1; i <= m; i++){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
e[++tot] = {a,b,c};
}
sort(e + 1,e + 1 + tot,cmp);
int L,R;
for(int i = 1; i <= n; i++)f[i] = i;
for(int i = 1; i <= tot; i++){
int fu = find(e[i].u);
int fv = find(e[i].v);
if(fu != fv)f[fu] = fv;
if(find(s) == find(t)){
L = e[i].w;
break;
}
}
for(int i = 1; i <= n; i++)f[i] = i;
sort(e + 1,e + 1 + tot,cmp2);
for(int i = 1; i <= tot; i++){
if(e[i].w < L)continue;
int fu = find(e[i].u);
int fv = find(e[i].v);
if(fu != fv)f[fu] = fv;
if(find(s) == find(t)){
R = e[i].w;break;
}
}
printf("%d %d\n",L,R);
}
int main(){
solved();
return 0;
}
京公网安备 11010502036488号