D - Menagerie
题意：n只动物从1到n围成一个圈，每只动物要么是羊要么是狼。每只动物会说出一个字母，说'o'表示它两边动物种类相同，说'x'表示不同。但羊是说真话，狼是说反话。求出这n只动物的种类。
tags：前几天做了个带权并查集的题，被自己坑了== 这题只要先假定好第1和第2只动物的种类(一共就4种情况)，就可以推出所有动物种类，再看推出的第1和第2只动物种类是否和假设的矛盾即可。
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define F(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 2e5+10;
int n, a[N];
char s[N];
int main()
{
scanf("%d %s", &n, s+1);
s[n+1]=s[1], s[n+2]=s[2];
FF(ca,0,1) FF(cb,0,1) {
a[1]=ca, a[2]=cb;
FF(i,2,n+1) {
if(a[i]==0) {
if(s[i]=='o') a[i+1]=a[i-1];
else a[i+1]=a[i-1]^1;
} else {
if(s[i]=='o') a[i+1]=a[i-1]^1;
else a[i+1]=a[i-1];
}
}
if(a[1]==a[n+1] && a[2]==a[n+2]) {
FF(i,1,n) printf("%c", a[i]==0?'S':'W');
return 0*puts("");
}
}
puts("-1");
return 0;
} E - Frequency
题意：一个数组a[]，要构造出一个最小字典序序列S。有两个操作：1、在数组a[]的最大几个数里，选出标号最小的数的标号id，加入到S的末尾；2、在a[]所有数里选择一个数，使其减1。 持续这两操作直到数组a[]都为0。问最后S里1~n每个数出现的次数。
tags：就是一个SB模拟，怎么就ZZ地没做出来呢== 排个序搞一下就行
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 2e5+10;
ll ans[N];
int n, minID;
struct P { int v, id; }p[N];
bool cmp(const P &a, const P &b) {
if(a.v==b.v) return a.id>b.id;
return a.v>b.v;
}
int main()
{
scanf("%d", &n);
rep(i,1,n) scanf("%d", &p[i].v), p[i].id=i;
sort(p+1, p+1+n, cmp);
minID=INF;
rep(i,1,n) {
minID=min(minID, p[i].id);
if(p[i].v!=p[i+1].v) ans[minID]+=1LL*(p[i].v-p[i+1].v)*i;
}
rep(i,1,n) printf("%lld\n", ans[i]);
return 0;
} 转载于:https://www.cnblogs.com/sbfhy/p/6420857.html