A. Splits
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
const long maxn=1e5;
const long mod=1e9+; int main()
{
long n,i;
scanf("%ld",&n);
printf("%ld",+n/);
return ;
}
B. Messages
贪心
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const long maxn=1e5;
const long mod=1e9+; int main()
{
long n,a,b,c,T,t,v,i,sum=;
scanf("%ld%ld%ld%ld%ld",&n,&a,&b,&c,&T);
sum=a*n;
for (i=;i<=n;i++)
{
scanf("%ld",&t);
if (b<=c)
sum=sum+(c-b)*(T-t);
}
cout<<sum<<endl;
return ;
}
C. Alternating Sum
快速幂 求逆元 等比数列
1. 1e9+9不是素数
2. 等比数列，公比可能为0
3. 数的数目为n+1
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const long maxn=1e5;
const long long mod=1e9+;
#define ll long long ll x,y; ll mul(ll s,long ci)
{
ll r=;
while (ci)
{
if ((ci & )==)
r=r*s%mod;
s=s*s%mod;
ci=ci>>;
}
return r;
} void gcd(ll a,ll b)
{
if (b==)
{
x=;
y=;
}
else
{
ll r;
gcd(b,a%b);
r=x;
x=y;
y=r-a/b*y;
}
} ll ni(ll s)
{
gcd(mod,s);
return (y%mod+mod)%mod;
} int main()
{
long n,k,i;
long long a,b,ni_a,ni_a_k,a_k,b_k,sum,c,d;
char ch;
scanf("%ld%lld%lld%ld\n",&n,&a,&b,&k);
c=mul(a,n); b_k=mul(b,k);
a_k=mul(a,k); ni_a=ni(a);
ni_a_k=ni(a_k); sum=;
for (i=;i<=k;i++)
{
scanf("%c",&ch);
if (ch=='+')
sum=(sum+c)%mod;
else
sum=(sum-c+mod)%mod;
} d=(n+)/k;
c=ni_a_k * b_k %mod; if (c==)
printf("%lld",sum*d%mod);
else
printf("%lld",sum* ((mul(c,d)%mod-+mod)%mod) %mod *ni(c-)%mod); return ;
}
D. Destruction of a Tree
树结构，从叶子向根，先确定子节点是否删边，然后父节点是否删边就可以确定，当根节点不删边，则成立，否则不成立
输出删点次序：从叶子向根，遇到需要删边的点，则删边，通过遍历所有的子辈节点，遇到不需要删除边的点，则输出，继续遍历，否则结束
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const long maxn=2e5+;
const long long mod=1e9+;
#define ll long long struct node
{
long d;
struct node *next;
}*point[maxn];
long need[maxn],fa[maxn];
bool vis[maxn],feng[maxn];
long pr[maxn],pr_count=; void dfs(long d)
{
long cc=;
vis[d]=true;
struct node *p=point[d];
while (p)
{
if (!vis[p->d])
{
cc++;
dfs(p->d);
need[d]=need[d] ^ need[p->d];
}
else
fa[d]=p->d;
p=p->next;
}
} void print(long d)
{
printf("%ld\n",d);
struct node *p=point[d];
while (p)
{
if (fa[d]!=p->d && need[p->d]==)
print(p->d);
p=p->next;
}
} void work(long d)
{
struct node *p=point[d];
struct node *q;
while (p)
{
if (fa[d]!=p->d)
work(p->d);
p=p->next;
}
if (need[d]==)
{
printf("%ld\n",d);
p=point[d];
while (p)
{
if (fa[d]!=p->d && need[p->d]==)
print(p->d);
p=p->next;
}
}
} int main()
{
struct node *p;
long n,root,i,y;
scanf("%ld",&n); for (i=;i<=n;i++)
{
point[i]=NULL;
need[i]=; //
vis[i]=false;
}
for (i=;i<=n;i++)
{
scanf("%ld",&y);
if (y==)
root=i;
else
{
p=(struct node *) malloc (sizeof(struct node));
p->d=y;
p->next=point[i];
point[i]=p; p=(struct node *) malloc (sizeof(struct node));
p->d=i;
p->next=point[y];
point[y]=p;
}
}
need[root]=; fa[root]=;
dfs(root);
if (need[root]==)
{
printf("NO");
return ;
} printf("YES\n");
work(root); return ;
}
/*
9
0 1 1 2 2 2 3 6 6 9
0 1 1 1 3 3 3 6 6 5
0 1 2 3 4
*/